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[1]

${\displaystyle \operatorname {Soph} _{c}(x):=\inf\{\operatorname {K} (S):x\in S\land \operatorname {K} (x\mid S)\geq \log _{2}(|S|)-c\land |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.