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
33 points
79 comments11 min readLW link

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

So8res20 Dec 2022 23:06 UTC
101 points
41 comments4 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
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
56 points
26 comments4 min readLW link

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

Abundant Output3 Oct 2021 3:23 UTC
22 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
68 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

Beyond Kol­mogorov and Shannon

25 Oct 2022 15:13 UTC
63 points
14 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

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

Morgan_Rogers2 Jul 2022 13:51 UTC
8 points
0 comments38 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

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

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

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

carado14 Dec 2022 18:55 UTC
14 points
0 comments7 min readLW link
(carado.moe)

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

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