Kolmogorov complexity: Difference between revisions

Revision as of 18:54, 24 May 2025

Revision as of 00:00, 25 May 2025

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 |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>

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==