Kolmogorov complexity: Difference between revisions

Revision as of 19:19, 15 March 2025

Revision as of 00:27, 27 March 2025

Line 385:

==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|url=https://archive.org/details/informationcompl00riss_364|url-access=limited|year=2007 |publisher=Springer S |year=2007 |isbn=978-0-387-68812-1 |page=[https://archive.org/details/informationcompl00riss_364/page/n59 53] |url-access=limited}}</ref><ref>{{cite book |author1=Ming Li |author2url=Paul Mhttps://link.Bspringer.com/book/10.1007/978-0-387-49820-1 Vitányi|title=An Introduction to Kolmogorov Complexity and Its Applications |urlauthor2=https://archivePaul M.org/details/introductiontoko00limi_695B. Vitányi |url-accesspublisher=limitedSpringer |year=2009|publisher=Springer |isbn=978-0-387-49820-1 |pages=[https://archive.org/details/introductiontoko00limi_695/page/n127 105]–106 |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>