# Kol­mogorov Complexity

TagLast edit: 21 Apr 2022 22:22 UTC by

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

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.

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

# Com­plex­ity and Intelligence

3 Nov 2008 20:27 UTC
33 points

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

20 Dec 2022 23:06 UTC
136 points

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

30 Jun 2023 5:15 UTC
25 points

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

26 Jul 2023 17:54 UTC
6 points

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

30 Jul 2023 14:33 UTC
−5 points

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

10 Mar 2022 20:26 UTC
15 points

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

13 Aug 2013 2:09 UTC
23 points

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

14 Apr 2012 20:59 UTC
5 points

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

20 Aug 2014 17:25 UTC
8 points

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

20 May 2010 17:11 UTC
12 points

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

11 Mar 2021 15:01 UTC
21 points

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

6 May 2021 22:16 UTC
68 points

# The Sim­ple World Hypothesis

5 Jun 2017 19:34 UTC
4 points

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

31 Dec 2017 20:15 UTC
16 points

# [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?

20 Dec 2023 15:36 UTC
11 points

# Beyond Kol­mogorov and Shannon

25 Oct 2022 15:13 UTC
60 points

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

14 Dec 2022 22:01 UTC
−3 points

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

7 Sep 2023 12:21 UTC
8 points

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

6 Nov 2017 20:08 UTC
0 points

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

13 Oct 2017 11:29 UTC
15 points

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

14 Feb 2016 8:38 UTC
6 points

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

26 Jun 2011 12:11 UTC
4 points

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

8 Jul 2013 4:30 UTC
26 points

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

5 Dec 2010 10:23 UTC
9 points

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

16 Feb 2012 1:51 UTC
18 points

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

5 Nov 2018 14:26 UTC
54 points

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

3 Oct 2021 3:23 UTC
28 points

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

5 Apr 2022 15:05 UTC
15 points

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

9 Aug 2012 7:19 UTC
7 points

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

13 Oct 2017 11:32 UTC
7 points

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

24 Oct 2017 12:03 UTC
1 point

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

20 Sep 2020 5:31 UTC
16 points

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

21 Aug 2023 21:02 UTC
22 points

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

12 Dec 2022 16:03 UTC
16 points

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

11 Sep 2023 16:44 UTC
13 points

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

1 Oct 2023 23:55 UTC
10 points

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

3 Aug 2023 0:58 UTC
5 points
(keplerlounge.com)

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

14 Dec 2022 18:55 UTC
15 points

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

2 Jul 2022 13:51 UTC
8 points

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

25 Feb 2023 9:00 UTC
−1 points

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

5 Aug 2022 4:43 UTC
3 points