HOME

TheInfoList



OR:

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 : \operatorname_c(x) := \inf \. 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