RSS

Kol­mogorov Complexity

TagLast edit: 21 Apr 2022 22:22 UTC by Alex_Altair

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: Solomonoff Induction, AIXI

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

Com­plex­ity and Intelligence

Eliezer Yudkowsky3 Nov 2008 20:27 UTC
32 points
79 comments11 min readLW link

Kol­mogorov com­plex­ity makes re­ward learn­ing worse

Stuart_Armstrong6 Nov 2017 20:08 UTC
0 points
0 comments1 min readLW link

Hu­mans can be as­signed any val­ues what­so­ever...

Stuart_Armstrong13 Oct 2017 11:29 UTC
14 points
6 comments4 min readLW link

Does Kol­mogorov com­plex­ity im­ply a bound on self-im­prov­ing AI?

contravariant14 Feb 2016 8:38 UTC
6 points
14 comments1 min readLW link

The Kol­mogorov com­plex­ity of a su­per­in­tel­li­gence

Thomas26 Jun 2011 12:11 UTC
4 points
30 comments1 min readLW link

Es­ti­mat­ing the kol­mogorov com­plex­ity of the known laws of physics?

Strilanc8 Jul 2013 4:30 UTC
17 points
46 comments1 min readLW link

Help re­quest: What is the Kol­mogorov com­plex­ity of com­putable ap­prox­i­ma­tions to AIXI?

AnnaSalamon5 Dec 2010 10:23 UTC
9 points
9 comments1 min readLW link

What is the ad­van­tage of the Kol­mogorov com­plex­ity prior?

skepsci16 Feb 2012 1:51 UTC
18 points
29 comments2 min readLW link

Hu­mans can be as­signed any val­ues what­so­ever…

Stuart_Armstrong5 Nov 2018 14:26 UTC
59 points
25 comments4 min readLW link

Oc­cam’s Ra­zor and the Univer­sal Prior

Peter Chatain3 Oct 2021 3:23 UTC
21 points
5 comments21 min readLW link

Are the fun­da­men­tal phys­i­cal con­stants com­putable?

Yair Halberstadt5 Apr 2022 15:05 UTC
15 points
6 comments2 min readLW link

From the “weird math ques­tions” de­part­ment...

CronoDAS9 Aug 2012 7:19 UTC
7 points
50 comments1 min readLW link

Hu­mans can be as­signed any val­ues what­so­ever...

Stuart_Armstrong13 Oct 2017 11:32 UTC
7 points
36 comments4 min readLW link

Hu­mans can be as­signed any val­ues what­so­ever...

Stuart_Armstrong24 Oct 2017 12:03 UTC
1 point
0 comments4 min readLW link

My (Mis)Ad­ven­tures With Al­gorith­mic Ma­chine Learning

AHartNtkn20 Sep 2020 5:31 UTC
16 points
4 comments41 min readLW link

Are Mag­i­cal Cat­e­gories Rel­a­tively Sim­ple?

jacobt14 Apr 2012 20:59 UTC
5 points
2 comments4 min readLW link

Thought ex­per­i­ments on sim­plic­ity in log­i­cal probability

Manfred20 Aug 2014 17:25 UTC
8 points
16 comments3 min readLW link

Devel­op­ment of Com­pres­sion Rate Method

Daniel_Burfoot20 May 2010 17:11 UTC
12 points
21 comments12 min readLW link

Be­hav­ioral Suffi­cient Statis­tics for Goal-Directedness

adamShimi11 Mar 2021 15:01 UTC
21 points
12 comments9 min readLW link

Pars­ing Chris Min­gard on Neu­ral Networks

Alex Flint6 May 2021 22:16 UTC
64 points
27 comments6 min readLW link

The Sim­ple World Hypothesis

DragonGod5 Jun 2017 19:34 UTC
4 points
15 comments8 min readLW link

A Can­di­date Com­plex­ity Measure

interstice31 Dec 2017 20:15 UTC
16 points
8 comments3 min readLW link

Does Check­ers have sim­pler rules than Go?

jefftk13 Aug 2013 2:09 UTC
23 points
47 comments1 min readLW link
No comments.