Kolmogorov complexity: Difference between revisions

Revision as of 22:06, 22 August 2024

Revision as of 07:18, 5 November 2024

Line 50:

Typically, inequalities with plain complexity have a term like <math>O(\min(\ln x, \ln y))</math> on one side, whereas the same inequalities with prefix-free complexity have only <math>O(1)</math>.

The main problem with plain complexity is that there is something extra sneaked into a program. A program not only representrepresents for something with its code, but also representrepresents its own length. In particular, a program <math>x</math> may represent a binary number up to <math>\log_2 |x|</math>, simply by its own length. Stated in another way, it is as if we are using a termination symbol to denote where a word ends, and so we are not using 2 symbols, but 3. To fix this defect, we introduce the prefix-free Kolmogorov complexity.<ref>(Downey and Hirschfeldt, 2010), Section 3.5</ref>

=== Prefix-free Kolmogorov complexity ''K'' ===