Kolmogorov complexity: Difference between revisions

Revision as of 18:54, 24 May 2025

Latest revision as of 07:35, 21 July 2025

(10 intermediate revisions by 9 users not shown)

Line 5:

The notion of Kolmogorov complexity can be used to state and [[Proof of impossibility|prove impossibility]] results akin to [[Cantor's diagonal argument]], [[Gödel's incompleteness theorem]], and [[halting problem|Turing's halting problem]].

In particular, no program ''P'' computing a [[lower bound]] for each text's Kolmogorov complexity can return a value essentially larger than ''P''<nowiki>'</nowiki>s own length (see section {{slink||Chaitin's incompleteness theorem}}); hence no single program can compute the exact Kolmogorov complexity for infinitely many texts. Kolmogorov complexity is the length of the ultimately compressed version of a file (i.e., anything which can be put in a computer). Formally, it is the length of a shortest program from which the file can be reconstructed. While Kolmogorov complexity is uncomputable, various approaches have been proposed and reviewed.<ref name="zenil20202">{{cite journal |last1=Zenil |first1=Hector |year=2020 |title=A Review of Methods for Estimating Algorithmic Complexity: Options, Challenges, and New Directions |journal=Entropy |volume=22 |issue=6 |pages=612 |doi=10.3390/e22060612 |doi-access=free |pmid=33286384 |pmc=7517143 }}</ref>

==Definition==

Line 37:

:''K''(''s'') = |''d''(''s'')|.

The length of the shortest description will depend on the choice of description language; but the effect of changing languages is bounded (a result called the ''invariance theorem'', see [[#invariance theorem|below]]).

=== Plain Kolmogorov complexity ''C'' ===

Line 142:

}}</ref>

Andrey Kolmogorov later [[multiple discovery|independently published]] this theorem in ''Problems Inform. Transmission'' in 1965.<ref>{{cite journal|volume=1 |issue=1 |year=1965 |pages=1–7 |title=Three Approaches to the Quantitative Definition of Information |url=http://www.ece.umd.edu/~abarg/ppi/contents/1-65-abstracts.html#1-65.2 |journal=Problems Inform. Transmission |first=A.N. |last=Kolmogorov |url-status=dead |archive-url=https://web.archive.org/web/20110928032821/http://www.ece.umd.edu/~abarg/ppi/contents/1-65-abstracts.html |archive-date=September 28, 2011 }}</ref> in 1965. [[Gregory Chaitin]] also presents this theorem in the ''J.[[Journal of the ACM]]''&nbsp;– Chaitin's paper was submitted October 1966 and revised in December 1968, and cites both Solomonoff's and Kolmogorov's papers.<ref>{{cite journal | last1 = Chaitin | first1 = Gregory J. | title = On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers| journal = Journal of the ACM | volume = 16 | pages = 407–422| year = 1969 | doi = 10.1145/321526.321530 | issue = 3| citeseerx = 10.1.1.15.3821 | s2cid = 12584692 }}</ref>

The theorem says that, among algorithms that decode strings from their descriptions (codes), there exists an optimal one. This algorithm, for all strings, allows codes as short as allowed by any other algorithm up to an additive constant that depends on the algorithms, but not on the strings themselves. Solomonoff used this algorithm and the code lengths it allows to define a "universal probability" of a string on which inductive inference of the subsequent digits of the string can be based. Kolmogorov used this theorem to define several functions of strings, including complexity, randomness, and information.

When Kolmogorov became aware of Solomonoff's work, he acknowledged Solomonoff's priority.<ref>{{cite journal | last1=Kolmogorov | first1=A. | title=Logical basis for information theory and probability theory | journal=IEEE Transactions on Information Theory | volume=14|issue=5 | pages=662–664 | year=1968 | doi =10.1109/TIT.1968.1054210 | s2cid=11402549 }}</ref> For several years, Solomonoff's work was better known in the Soviet Union than in the Western WorldWest. The general consensus in the scientific community, however, was to associate this type of complexity with Kolmogorov, who was concerned with randomness of a sequence, while Algorithmic Probability became associated with Solomonoff, who focused on prediction using his invention of the universal prior probability distribution. The broader area encompassing descriptional complexity and probability is often called Kolmogorov complexity. The computer scientist [[Ming Li]] considers this an example of the [[Matthew effect (sociology)|Matthew effect]]: "...to everyone who has, more will be given..."<ref>{{Cite book |doi=10.1007/978-0-387-49820-1_1 |chapter=Preliminaries |title=An Introduction to Kolmogorov Complexity and its Applications |url=https://archive.org/details/introductiontoko00limi_695 |url-access=limited |pages=[https://archive.org/details/introductiontoko00limi_695/page/n23 1]–99 |series=Texts in Computer Science |year=2008 |last1=Li |first1=Ming |last2=Vitányi |first2=Paul |isbn=978-0-387-33998-6 }}</ref>

There are several other variants of Kolmogorov complexity or algorithmic information. The most widely used one is based on [[self-delimiting program]]s, and is mainly due to [[Leonid Levin]] (1974).

Line 152:

An axiomatic approach to Kolmogorov complexity based on [[Blum axioms]] (Blum 1967) was introduced by Mark Burgin in the paper presented for publication by Andrey Kolmogorov.<ref name=Burgin1982>{{cite journal |last=Burgin |first=M. |year=1982 |title=Generalized Kolmogorov complexity and duality in theory of computations |journal=Notices of the Russian Academy of Sciences |volume=25 |issue=3 |pages=19–23 |url=https://www.mathnet.ru/eng/dan45265}}</ref>

In the late 1990s and early 2000s, methods developed to approximate Kolmogorov complexity relied on popular compression algorithms like LZW,<ref name="zenil20202">{{cite journal |last1=Zenil |first1=Hector |year=2020 |title=A Review of Methods for Estimating Algorithmic Complexity: Options, Challenges, and New Directions |journal=Entropy |volume=22 |issue=6 |pages=612 |doi=10.3390/e22060612 |doi-access=free |pmid=33286384 |pmc=7517143 }}</ref> which made difficult or impossible to provide any estimation to short strings until a method based on [[Algorithmic probability]] was introduced,<ref>{{cite journal |last1=Delahaye |first1=Jean-Paul |last2=Zenil |first2=Hector |title=Numerical evaluation of algorithmic complexity for short strings: A glance into the innermost structure of randomness |journal=Applied Mathematics and Computation |volume=219 |issue=1 |pages=63–77 |year=2012 |doi=10.1016/j.amc.2011.09.020 |url=https://www.sciencedirect.com/science/article/pii/S0096300311012367 }}</ref><ref>{{cite journal |last1=Soler-Toscano |first1=Fernando |last2=Zenil |first2=Hector |last3=Delahaye |first3=Jean-Paul |last4=Gauvrit |first4=Nicolas |title=Calculating Kolmogorov Complexity from the Output Frequency Distributions of Small Turing Machines |journal=PLOS ONE |volume=9 |issue=5 |pages=74–85 |year=2014 |doi=10.1371/journal.pone.0096223 |doi-access=free |pmid=24787763 |pmc=4013017 |bibcode=2014PLoSO...996223S }}</ref> offering the only alternative to compression-based methods.<ref>Zenil, Hector; Soler Toscano, Fernando; Gauvrit, Nicolas (2022). "Methods and Applications of Algorithmic Complexity: Beyond Statistical Lossless Compression". <i>''Emergence, Complexity and Computation</i>''. Springer Berlin, Heidelberg. doi:10.1007/978-3-662-64985-5. ISBN 978-3-662-64983-1.

</ref>

Line 384:

==Implications in biology==

In the context of biology to argue that the symmetries and modular arrangements observed in multiple species emerge from the tendency of evolution to prefer minimal Kolmogorov complexity.<ref>{{Cite journal |lastlast1=Johnston |firstfirst1=Iain G. |last2=Dingle |first2=Kamaludin |last3=Greenbury |first3=Sam F. |last4=Camargo |first4=Chico Q. |last5=Doye |first5=Jonathan P. K. |last6=Ahnert |first6=Sebastian E. |last7=Louis |first7=Ard A. |date=2022-03-15 |title=Symmetry and simplicity spontaneously emerge from the algorithmic nature of evolution |url=https://www.pnas.org/doi/full/10.1073/pnas.2113883119 |journal=Proceedings of the National Academy of Sciences |volume=119 |issue=11 |pages=e2113883119 |doi=10.1073/pnas.2113883119 |doi-access=free |pmc=8931234 |pmid=35275794|bibcode=2022PNAS..11913883J }}</ref> Considering the genome as a program that must solve a task or implement a series of functions, shorter programs would be preferred on the basis that they are easier to find by the mechanisms of evolution.<ref>{{Cite journal |last=Alon |first=Uri |date=Mar 2007 |title=Simplicity in biology |url=https://www.nature.com/articles/446497a |journal=Nature |language=en |volume=446 |issue=7135 |pages=497–497497 |doi=10.1038/446497a |pmid=17392770 |bibcode=2007Natur.446..497A |issn=1476-4687}}</ref> An example of this approach is the eight-fold symmetry of the compass circuit that is found across insect species, which correspond to the circuit that is both functional and requires the minimum Kolmogorov complexity to be generated from self-replicating units.<ref>{{Cite journal |lastlast1=Vilimelis Aceituno |firstfirst1=Pau |last2=Dall'Osto |first2=Dominic |last3=Pisokas |first3=Ioannis |date=2024-05-30 |editor-last=Colgin |editor-first=Laura L |editor2-last=Vafidis |editor2-first=Pantelis |title=Theoretical principles explain the structure of the insect head direction circuit |url=https://elifesciences.org/articles/91533 |journal=eLife |volume=13 |pages=e91533 |doi=10.7554/eLife.91533 |doi-access=free |pmid=38814703 |pmc=11139481 |issn=2050-084X}}</ref>

==Conditional versions==

{{expand section|date=July 2014}}

The conditional Kolmogorov complexity of two strings <math>K(x|y)</math> is, roughly speaking, defined as the Kolmogorov complexity of ''x'' given ''y'' as an auxiliary input to the procedure.<ref name="Rissanen2007">{{cite book |author=Jorma Rissanen |url=https://link.springer.com/book/10.1007/978-0-387-68812-1 |title=Information and Complexity in Statistical Modeling |series=Information Science and Statistics |publisher=Springer S |year=2007 |isbn=978-0-387-68812-1 |page=[https://archive.org/details/informationcompl00riss_364/page/n59 53] |doi=10.1007/978-0-387-68812-1 |url-access=limited}}</ref><ref>{{cite book |author1=Ming Li |url=https://link.springer.com/book/10.1007/978-0-387-49820-1 |title=An Introduction to Kolmogorov Complexity and Its Applications |author2=Paul M.B. Vitányi |publisher=Springer |year=2009 |isbn=978-0-387-49820-1 |pages=[https://archive.org/details/introductiontoko00limi_695/page/n127 105]–106 |doi=10.1007/978-0-387-49820-1 |url-access=limited}}</ref> So while the (unconditional) Kolmogorov complexity <math>K(x)</math> of a sequence <math>x</math> is the length of the shortest binary program that outputs <math>x</math> on a universal computer and can be thought of as the minimal amount of information necessary to produce <math>x</math>, the conditional Kolmogorov complexity <math>K(x|y)</math> is defined as the length of the shortest binary program that computes <math>x</math> when <math>y</math> is given as input, using a universal computer.<ref>{{Cite book |url=https://www.worldcat.org/title/181069666 |title=Computational intelligence in medical informatics |date=2008 |publisher=Springer |isbn=978-3-540-75766-5 |editor-last=Kelemen |editor-first=Árpád |___location=New York ; London |pages=160 |oclc=181069666 |editor-last2=Abraham |editor-first2=Ajith |editor-last3=Liang |editor-first3=Yulan}}</ref>

There is also a length-conditional complexity <math>K(x|L(x))</math>, which is the complexity of ''x'' given the length of ''x'' as known/input.<ref>{{cite book|author1=Ming Li|author2=Paul M.B. Vitányi|title=An Introduction to Kolmogorov Complexity and Its Applications|url=https://archive.org/details/introductiontoko00limi_695|url-access=limited|year=2009|publisher=Springer |isbn=978-0-387-49820-1|page=[https://archive.org/details/introductiontoko00limi_695/page/n141 119]}}</ref><ref>{{cite journal |doi=10.1016/j.tcs.2013.07.009 |title=Conditional Kolmogorov complexity and universal probability |journal=Theoretical Computer Science |volume=501 |pages=93–100 |year=2013 |last1=Vitányi |first1=Paul M.B. |url=https://ir.cwi.nl/pub/26818 |arxiv=1206.0983 |s2cid=12085503 }}</ref>

== Time-bounded complexity ==

Time-bounded Kolmogorov complexity is a modified version of Kolmogorov complexity where the space of programs to be searched for a solution is confined to only programs that can run within some pre-defined number of steps.<ref>{{Cite journal |last1=Hirahara |first1=Shuichi |last2=Kabanets |first2=Valentine |last3=Lu |first3=Zhenjian |last4=Oliveira |first4=Igor C. |date=2024 |title=Exact Search-To-Decision Reductions for Time-Bounded Kolmogorov Complexity |journal=39th Computational Complexity Conference (CCC 2024) |series=Leibniz International Proceedings in Informatics (LIPIcs) |volume=300 |language=en |publisher=Schloss Dagstuhl – Leibniz-Zentrum für Informatik |pages=29:1–29:56 |doi=10.4230/LIPIcs.CCC.2024.29|doi-access=free |isbn=978-3-95977-331-7 }}</ref> It is hypothesised that the possibility of the existence of an efficient algorithm for determining approximate time-bounded Kolmogorov complexity is related to the question of whether true [[one-way function]]s exist.<ref>{{Cite web |last=Klarreich |first=Erica |date=2022-04-06 |title=Researchers Identify 'Master Problem' Underlying All Cryptography |url=https://www.quantamagazine.org/researchers-identify-master-problem-underlying-all-cryptography-20220406/ |access-date=2024-11-16 |website=Quanta Magazine |language=en}}</ref><ref>{{Citation |last1=Liu |first1=Yanyi |title=On One-way Functions and Kolmogorov Complexity |date=2020-09-24 |arxiv=2009.11514 |last2=Pass |first2=Rafael}}</ref>

==See also==