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.


  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://​​​​viewdoc/​​download?doi=

  3. LI, Ming. & VITANY, Paul. “Algorithmic Complexity”. Available at: http://​​​​~paulv/​​papers/​​020608isb.pdf

Com­plex­ity and Intelligence

Eliezer Yudkowsky3 Nov 2008 20:27 UTC
33 points
78 comments11 min readLW link

K-com­plex­ity is silly; use cross-en­tropy instead

So8res20 Dec 2022 23:06 UTC
136 points
53 comments4 min readLW link2 reviews

Con­tra An­ton 🏴‍☠️ on Kol­mogorov com­plex­ity and re­cur­sive self improvement

DaemonicSigil30 Jun 2023 5:15 UTC
25 points
12 comments2 min readLW link

Why you can’t treat de­cid­abil­ity and com­plex­ity as a con­stant (Post #1)

Noosphere8926 Jul 2023 17:54 UTC
6 points
13 comments5 min readLW link

Hilbert’s Triumph, Church and Tur­ing’s failure, and what it means (Post #2)

Noosphere8930 Jul 2023 14:33 UTC
−5 points
16 comments15 min readLW link

Al­gorith­mic Mea­sure of Emer­gence v2.0

interstice10 Mar 2022 20:26 UTC
15 points
2 comments4 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

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
68 points
26 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

[Question] What’s the min­i­mal ad­di­tive con­stant for Kol­mogorov Com­plex­ity that a pro­gram­ming lan­guage can achieve?

Noosphere8920 Dec 2023 15:36 UTC
11 points
15 comments1 min readLW link

Beyond Kol­mogorov and Shannon

25 Oct 2022 15:13 UTC
60 points
17 comments5 min readLW link

Kol­mogorov Com­plex­ity and Si­mu­la­tion Hypothesis

False Name14 Dec 2022 22:01 UTC
−3 points
0 comments7 min readLW link

[Question] Mea­sure of com­plex­ity al­lowed by the laws of the uni­verse and rel­a­tive the­ory?

dr_s7 Sep 2023 12:21 UTC
8 points
22 comments1 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
15 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
26 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
54 points
27 comments4 min readLW link

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

Peter Chatain3 Oct 2021 3:23 UTC
28 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
1 comment4 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

Causal­ity and a Cost Se­man­tics for Neu­ral Networks

scottviteri21 Aug 2023 21:02 UTC
22 points
1 comment9 min readLW link

Mean­ingful things are those the uni­verse pos­sesses a se­man­tics for

Abhimanyu Pallavi Sudhir12 Dec 2022 16:03 UTC
16 points
14 comments14 min readLW link

Erdős Prob­lems in Al­gorith­mic Probability

Aidan Rocke11 Sep 2023 16:44 UTC
13 points
4 comments2 min readLW link

Re­vis­it­ing the Man­i­fold Hypothesis

Aidan Rocke1 Oct 2023 23:55 UTC
10 points
19 comments4 min readLW link

Kol­mogorov’s the­ory of Al­gorith­mic Probability

Aidan Rocke3 Aug 2023 0:58 UTC
5 points
2 comments2 min readLW link

all claw, no world — and other thoughts on the uni­ver­sal distribution

Tamsin Leake14 Dec 2022 18:55 UTC
15 points
0 comments7 min readLW link

Goal-di­rect­ed­ness: tack­ling complexity

Morgan_Rogers2 Jul 2022 13:51 UTC
8 points
0 comments38 min readLW link

Just How Hard a Prob­lem is Align­ment?

Roger Dearnaley25 Feb 2023 9:00 UTC
−1 points
1 comment21 min readLW link

An at­tempt to un­der­stand the Com­plex­ity of Values

Dalton Mabery5 Aug 2022 4:43 UTC
3 points
0 comments5 min readLW link

Goal-di­rect­ed­ness: rel­a­tivis­ing complexity

Morgan_Rogers18 Aug 2022 9:48 UTC
3 points
0 comments11 min readLW link

Take­aways from a Mechanis­tic In­ter­pretabil­ity pro­ject on “For­bid­den Facts”

15 Dec 2023 11:05 UTC
33 points
8 comments10 min readLW link
No comments.