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

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.