In
algorithmic information theory
Algorithmic information theory (AIT) is a branch of theoretical computer science that concerns itself with the relationship between computation and information of computably generated objects (as opposed to stochastically generated), such as st ...
, sophistication is a measure of complexity related to
algorithmic entropy.
When K is the
Kolmogorov complexity
In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program (in a predetermined programming language) that prod ...
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.
See also
*
Logical depth Logical depth is a measure of complexity for individual strings devised by Charles H. Bennett based on the computational complexity of an algorithm that can recreate a given piece of information. It differs from Kolmogorov complexity in that it ...
References
Further reading
*
*
*
External links
The First Law of Complexodynamics
Measures of complexity
{{comp-sci-theory-stub