Content deleted Content added
Partly undid revision 1295292631 by 2601:645:8300:43E0:5CA4:847:4ECB:97E4: link is a good idea, but respect WP:EASTEREGG |
added a paragraph to conditional Kolmogorov complexity (including reference) |
||
Line 388:
==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>
| |||