Logical depth is a measure of

complexity Complexity characterises the behaviour of a system or model whose components interaction, interact in multiple ways and follow local rules, leading to nonlinearity, randomness, collective dynamics, hierarchy, and emergence. The term is generall ...

for individual strings devised by Charles H. Bennett based on the

computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...

of an algorithm that can recreate a given piece of information. It differs from Kolmogorov complexity in that it considers the computation time of the algorithm with nearly minimal length, rather than the length of the minimal algorithm. Formally, in the context of some universal computer

U

the logical depth of a string

x

to significance level

s

is given by

\text\,

the running time of the fastest program that produces

x

and is no more than

s

longer than the minimal program.

References

* * Information theory Computational complexity theory Measures of complexity {{Comp-sci-theory-stub

See also

References