Content deleted Content added
m Undid edits by 14.139.38.137 (talk) to last version by WikiCleanerBot: editing tests |
m →Plain Kolmogorov complexity C: add crossref to Prefix code |
||
Line 40:
=== Plain Kolmogorov complexity ''C'' ===
There are two definitions of Kolmogorov complexity: ''plain'' and ''prefix-free''. The plain complexity is the minimal description length of any program, and denoted <math>C(x)</math> while the prefix-free complexity is the minimal description length of any program encoded in a [[prefix code|prefix-free code]], and denoted <math>K(x)</math>. The plain complexity is more intuitive, but the prefix-free complexity is easier to study.
By default, all equations hold only up to an additive constant. For example, <math>f(x) = g(x)</math> really means that <math>f(x) = g(x) + O(1)</math>, that is, <math>\exists c, \forall x, |f(x) - g(x)| \leq c</math>.
| |||