Supriya Ghosh (Editor)

Sophistication (complexity theory)

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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

Soph c ⁡ ( x ) := inf { K ⁡ ( S ) : x ∈ S ∧ K ⁡ ( x ∣ S ) ≥ log 2 ⁡ ( | S | ) − c ∧ | S | ∈ 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.

References

Sophistication (complexity theory) Wikipedia


Similar Topics
×