Sophistication (complexity theory)

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

$\operatorname{Soph}_c(x) := \inf \{ \operatorname{K}(S) : x \in S \land K(x|S) \ge \log_2(|S|) - c \land |S| \in \mathbb{N}_+ \}$^[1]

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

• Logical depth

References

1. Mota, Francisco; Aaronson, Scott; Antunes, Luís; Souto, André. "Sophistication as Randomness Deficiency" (PDF). doi:10.1007/978-3-642-39310-5_17.

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" (PDF). doi:10.1007/s00224-007-9095-5.
• Luís, Antunes; Bauwens, Bruno; Souto, André; Teixeira, Andreia (2013). "Sophistication vs Logical Depth". arXiv:1304.8046.

External links

• The First Law of Complexodynamics