Kolmogorovkomplexitás

Kolmogorov-komplexitás olyan algoritmikus információelméleti mérték, amely egy adott universális leíró nyelvhez (általában egy univerzális Turing-géphez) kötött x sztring kiírásához és megállásához a legrövidebb programhosságot méri. Más szóval K_U(x) az x kiadása érdekében szükséges legrövidebb bemenet hossza a kiválasztott univerzális géphez. A definíció a választott leíró nyelv függvényében lehet, de az invariancia-tétel szerint különbségük állandóval el van rejtve: K_U(x) és K_V(x) között van egy állandó c, hogy K_U(x) ≤ K_V(x) + c minden x esetén.

A Kolmogorov-komplexitás megállapíthatósága nemáltalánítható: nincs általános algoritmus, amely minden x-re megmondaná K_U(x) értékét. Ennek oka a megállási probléma és a véges hosszúságú programokra vonatkozó visszanyomási érvelés. Ennek ellenére a fogalom rendkívül hasznos elméleti eszköz az információtartalom és a véletlenszerűség formális vizsgálatára.

Az incompressibilitás és a véletlenszerűség összefüggése: n hosszú x esetén a legtöbb x incompressibilis, azaz K(x) ≥ n − c néhány állandóval; azaz a tipikus sztringek nem tömöríthetők rövidebb programmal. Ezzel szemben létezik olyan sztring is, amely jelentősen rövidebb programmal kiírható, ez a strukturált vagy determinisztikus mintákat mutatja.

Varianták és kiterjesztések közé tartozik a tiszta (plain) és a prefix-közeli (prefix) Kolmogorov-komplexitás, valamint a feltételes komplexitás K(x|y). A fogalom alapvető az algoritmikus információelméletben, és összekapcsolható a Martin-Löf valószínűségi véletlenség fogalmával és Levin-típusú észlelési eredményekkel; ugyanakkor gyakorlati alkalmazásokra csak korlátozott mértékben használható közvetlenül, mivel nem computable, és helyettesíthetők korlátozott tömörítési/alsó-becslésekkel.