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

${\mathrm{Soph}}_c(x):=\inf \{\mathrm{K}(S):x\in S\wedge \mathrm{K}(x\mid S)\ge {\log }_2(|S|)-c\wedge |S|\in {\mathbb{N}}_{+}\}.$

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

Further reading

• Template:Cite journal
• Template:Cite journal
• Template:Cite arXiv

External links

• The First Law of Complexodynamics

Template:Comp-sci-theory-stub