LESSWRONG
LW

Wikitags

Kolmogorov Complexity

Edited by joaolkf, Kaj_Sotala, et al. last updated 21st Apr 2022

The Kolmogorov Complexity (sometimes called Algorithmic Complexity) of a set of data is the size of the shortest possible description of the data.

See also: ,

Algorithmic complexity is an inverse measure of compressibility. If the data is complex and random, the shortest possible description of it becomes longer. This is also one of the best definitions of randomness so far1. If the data has few regular patterns, it is difficult to compress it or describe it shortly, giving it a high Kolmogorov complexity and randomness. If there isn't any way to describe the data so that the description is shorter than the data itself, the data is incompressible. 2

More formally, the Kolmogorov complexity C(x) of a set x, is the size in bits of the shortest binary program (in a fixed programming language) that prints the set x as its only output. If C(x) is equal or greater than the size of x in bits, x is incompressible. 3

This notion can be used to state many important results in computational theory. Possibly the most famous is Chaitin's incompleteness theorem, a version of Gödel’s incompleteness theorem.

References

  1. SIPSER, M. (1983) "A complexity theoretic approach to randomness". In Proceedings of the 15th ACM Symposium on the Theory of Computing, pages 330{335. ACM, New York.↩
  2. FORTNOW, Lance. "Kolmogorov Complexity" Available at: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.120.4949&rep=rep1&type=pdf↩
  3. LI, Ming. & VITANY, Paul. “Algorithmic Complexity”. Available at: http://homepages.cwi.nl/~paulv/papers/020608isb.pdf↩
Solomonoff Induction
Subscribe
4
Subscribe
4
Discussion0
Discussion0
AIXI
Posts tagged Kolmogorov Complexity
34Complexity and Intelligence
Eliezer Yudkowsky
17y
78
147K-complexity is silly; use cross-entropy instead
So8res
3y
54
69Parsing Chris Mingard on Neural Networks
Ω
Alex Flint
4y
Ω
26
62Beyond Kolmogorov and Shannon
Ω
Alexander Gietelink Oldenziel, Adam Shai
3y
Ω
22
54Humans can be assigned any values whatsoever…
Ω
Stuart_Armstrong
7y
Ω
27
29Occam's Razor and the Universal Prior
Peter Chatain
4y
5
26Estimating the kolmogorov complexity of the known laws of physics?
Strilanc
12y
51
25Contra Anton 🏴‍☠️ on Kolmogorov complexity and recursive self improvement
DaemonicSigil
2y
12
25Take over my project: do computable agents plan against the universal distribution pessimistically?
Q
Cole Wyeth
5mo
Q
3
23Does Checkers have simpler rules than Go?
jefftk
12y
47
21Behavioral Sufficient Statistics for Goal-Directedness
Ω
adamShimi
4y
Ω
12
20The Croissant Principle: A Theory of AI Generalization
Jeffrey Liang
20d
6
18What is the advantage of the Kolmogorov complexity prior?
skepsci
13y
29
16Humans can be assigned any values whatsoever...
Stuart_Armstrong
8y
6
16A Candidate Complexity Measure
interstice
8y
8
Load More (15/48)
Add Posts