Sophistication (complexity theory)
From HandWiki
In algorithmic information theory, sophistication is a measure of complexity related to algorithmic entropy. When K is the Kolmogorov complexity and c is a constant, the sophistication of x can be defined as[1]
- [math]\displaystyle{ \operatorname{Soph}_c(x) := \inf \{ \operatorname{K}(S) : x \in S \land \operatorname{K}(x\mid S) \ge \log_2(|S|) - c \land |S| \in \mathbb{N}_+ \}. }[/math]
The constant c is called significance. The S variable ranges over finite sets.
Intuitively, sophistication measures the complexity of a set of which the object is a "generic" member.
See also
References
- ↑ Mota, Francisco; Aaronson, Scott; Antunes, Luís; Souto, André (2013). "Sophistication as Randomness Deficiency". Descriptional Complexity of Formal Systems. Lecture Notes in Computer Science. 8031. pp. 172–181. doi:10.1007/978-3-642-39310-5_17. ISBN 978-3-642-39309-9. http://www.scottaaronson.com/papers/DCFS-Final.pdf.
Further reading
- Koppel, Moshe (1995). Herken, Rolf. ed. "Structure". The Universal Turing Machine (2nd Ed.) (Springer-Verlag New York, Inc.): 403–419. ISBN 3-211-82637-8.
- Antunes, Luís; Fortnow, Lance (August 30, 2007). "Sophistication Revisited". Theory of Computing Systems 45: 150–161. doi:10.1007/s00224-007-9095-5. http://people.cs.uchicago.edu/~fortnow/papers/soph.pdf.
- Luís, Antunes; Bauwens, Bruno; Souto, André; Teixeira, Andreia (2013). "Sophistication vs Logical Depth". arXiv:1304.8046 [cs.IT].
External links
 |  |
