Kolmogorovova složitost

V teoretické informatice a matematice , přesněji v teorii informací , je Kolmogorovova složitost neboli náhodná složitost nebo algoritmická složitost objektu - číslo, digitální obraz , řetězec - velikost nejmenšího algoritmu (v určitém pevném programovacím jazyce ) který generuje tento objekt. Je pojmenována po matematikovi Andreji Kolmogorovovi , který na toto téma publikoval již v roce 1963. Někdy se mu také říká Kolmogorovova-Solomonoffova složitost . Tuto veličinu lze považovat za hodnocení formy složitosti objektu.

Příklady

První příklad - textové řetězce

Zvažte dva texty, každý složený z 32 znaků:

abababababababababababababababab a 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

První z těchto dvou textů lze generovat abalgoritmem „16krát“, jinými slovy algoritmem o délce 10 znaků, zatímco druhý se nezdá mít žádný malý algoritmus, který by jej generoval kromě algoritmu, který se skládá z tohoto zápisu řetězec znaků, to znamená algoritmus o 32 znacích. Zdá se tedy, že první text má Kolmogorovovu složitost menší než druhý.

Druhý příklad - obrázek

Obrázek vpravo ukazuje bitmapový obrázek, který zobrazuje sadu Mandelbrot . Tento 24bitový obrázek váží 1,61 MB. Na druhou stranu, malý algoritmus může tento obraz reprodukovat z matematické definice Mandelbrotovy množiny a souřadnic rohů obrazu. Takže Kolmogorovova složitost (nekomprimovaného) bitmapového obrazu je v rozumném výpočetním modelu menší než 1,61 megabajtů.

Definice

Zvažte počítačový stroj $M$ schopný vykonávat programy. O tomto stroji se říká, že je univerzální, když dokáže emulovat jakýkoli jiný počítačový stroj. Stroj univerzální Turingův je příkladem.

Označíme- $P M$ všechny programy napsané pro stroj $M$ . U programu $p \in P M$ označíme $l ( p )$ jeho délku v počtu instrukcí pro stroj $M$ a $s ( p )$ jeho výstup. Kolmogorovova složitost $K M ( x )$ neboli algoritmická složitost konečné posloupnosti $x$ znaků pro stroj $M$ je definována:

K_M (x) = \ min_ {p \ in P_M} \ {l (p), s (p) = x \}

Je to tedy délka nejmenšího programu napsaného pro stroj $M,$ který generuje sekvenci $x$ . Konstantní sekvence má nízkou složitost, protože programy, které ji generují, mohou být velmi krátké.

Zbývá zjistit, do jaké míry závisí funkce $K M ( x )$ na stroji $M$ , protože je docela možné si představit stroj, který má jednoduché instrukce pro generování určitých složitých sekvencí. Odpověď je následující: existuje univerzální stroj $U$ (často nazývaný aditivně optimální), takže pro jakýkoli stroj $M$ existuje konstanta $c M$ ověřující pro jakoukoli sekvenci $x$ nerovnost:

K_U (x) \ leq K_M (x) + c_M

Intuitivně, $c M$ je délka pláště (nebo emulátoru ), psaný pro stroj $U$ , jazyk, který používá zařízení $M$ . Mluvíme pak o univerzálnosti Kolmogorovovy složitosti v tom smyslu, že nezávisí, s výjimkou aditivní konstanty, na uvažovaném stroji.

Sekvence pak může být považována za čím „náhodnější“, čím větší je její složitost ve srovnání s její velikostí. Z tohoto pohledu nejsou desetinná čísla čísel $π$ , $e$ nebo √ 2 opravdu náhodná, protože pro jejich výpočet existují velmi jednoduché algoritmy.

Další obtíž spočívá ve skutečnosti, že Kolmogorovova složitost není rozhodnutelná : můžeme dát algoritmus vytvářející požadovaný objekt, což dokazuje, že složitost tohoto objektu je nanejvýš velikostí tohoto algoritmu. Ale nemůžete napsat program, který dává Kolmogorovovu složitost jakéhokoli objektu, který mu chcete dát jako vstup.

Koncept, s nímž se zachází opatrně, se přesto ukazuje jako zdroj mnoha teoretických výsledků.

Například, jeden volá nestlačitelné číslo ve smyslu Kolmogorova reálného, jehož p-adický vývoj (binární pro větší pohodlí) je srovnatelný s velikostí algoritmu, který umožňuje jeho výpočet. V tomto smyslu jsou všechny racionální a některé iracionální stlačitelné, zejména transcendentní čísla jako $π$ , $e$ nebo 0,12345678910111213… jejichž binární expanze je nekonečná, ale posloupnost desetinných míst je dokonale vypočítatelná. Na druhou stranu takzvané Chaitinovo číslo $Ω$ není: toto číslo měří pravděpodobnost, že se stroj dodávaný programem složeným z náhodných bitů zastaví. Topologie nestlačitelných čísel je zajímavé: jsme intuitivně pochopit, že tato množina je hustá v , ale to je nemožné, aby algoritmicky vykazují nestlačitelnou real, protože to by znamenalo dávat to efektivní metodu výpočtu. Navíc můžeme ukázat, že všechna nestlačitelná čísla jsou normální , posloupnost jejich desetinných míst musí být v silném smyslu náhodná. $\ mathbb {R}$

Vlastnosti

Kolmogorovovu složitost nelze vypočítat . Jinými slovy, neexistuje žádný počítačový program, který bere s jako vstup a vrací K ( s ). Abychom to dokázali, uvažujme absurdně a předpokládejme, že taková Kolmoova funkce existuje. Označíme k velikost této funkce (tj. Počet znaků jejího zdrojového kódu). Pak bychom mohli napsat následující algoritmus:

n := 1 Tant que Kolmo(n) < k + 100 faire: n := n + 1 Fin du Tant que écrire n

Tento algoritmus tedy zapisuje nejmenší číslo, aby měla Kolmogorovovu složitost větší než k + 100 (toto číslo nutně existuje, protože existuje pouze konečný počet programů o velikosti menší než k + 100 a existuje nekonečno přirozených čísel).

Výše uvedený algoritmus je ale napsán přesně s méně než k + 100 znaky: je tedy složitější než k + 100 a přesně zapisuje řadu složitosti větší než k + 100, což je absurdní (tuto poznámku můžeme přiblížit k argumentu použitému pro Berryho paradox ).

Neexistuje tedy žádná funkce, která vypočítá Kolmogorovovu složitost.

Varianty s omezenými prostředky

Definice Kolmogorovovy složitosti je definována jako nejmenší program, který produkuje x. Ale tento program by mohl spotřebovat značné zdroje. Proto je důležité brát v úvahu zdroje použité programem. Nechť U je univerzální stroj. Zde je verze ohraničená časem t:

${\ displaystyle C ^ {t} (x) = \ min _ {p} \ {| p |: U (p) {\ text {písemný}} x {\ text {en}} t (| x |) { \ text {kroky}} \}}$

Je třeba poznamenat, že časová složitost je definována jako funkce výstupu x a nikoli velikosti programu p. Sipser v roce 1983 navrhl míru velikosti nejmenšího programu, která rozlišuje řetězec znaků x. Buhrman, Fortnow a Laplante v roce 2002 poskytli nedeterministickou verzi, přičemž použili nedeterministický univerzální stroj. Další definice lze nalézt v Levin , a v Allenderu, kde definice složitosti je součtem Kolmogorovovy složitosti a příspěvku časové složitosti.

Souvislost s teorií složitosti algoritmu

Vazby mezi Kolmogorovovou složitostí a teorií složitosti byly vytvořeny pomocí následující sady jako věštce :

R = sada řetězců znaků x, jejichž Kolmogorovova složitost je alespoň | x | / 2

V roce 2002, Allender Buhrman, Koucký van Melkebeek a Ronnerbuger ukazují, že PSPACE je součástí P R a EXPTIME je součástí NP R . Pak, v roce 2004, Allender Buhrman, Koucký prokázat, s použitím stejných technik, které NEXPTIME je součástí NP R .

Poznámky a odkazy

Část tohoto článku (nebo dřívější verze) je převzata z „ Malé příručky pro použití agregátů připravujících orálně stochastické modelování “, kterou napsal Djèlil Chafaï a publikoval pod GFDL .

Poznámky

Reference

Andrey Kolmogorov , „ Na stolech náhodných čísel “, Sankhya Ser. A. , sv. 25,1963, str. 369–375 ( Math Reviews 178484 )
Andrey Kolmogorov , „ Na tabulkách náhodných čísel “, Theoretical Computer Science , sv. 207, n O 21998, str. 387–395 ( DOI 10.1016 / S0304-3975 (98) 00075-9 , matematické recenze 1643414 )
Stránka s popisem souboru na Wikimedia Commons .
(en-GB) Osamu Watanabe , Kolmogorovova složitost a výpočetní složitost , kol. "Monografie EATCS o teoretické informatice",1992( ISBN 978-3-642-77737-0 , DOI 10.1007 / 978-3-642-77735-6 , číst online )
Michael Sipser , „ Složitost teoretického přístupu k náhodnosti “, Sborník z 15. ročníku sympozia ACM o teorii výpočetní techniky , ACM, sTOC '83,1983, str. 330–335 ( ISBN 9780897910996 , DOI 10.1145 / 800061.808762 , číst online , přístup k 14. červenci 2019 )
H. Buhrman , L. Fortnow a S. Laplante , „ Resource-Bounded Kolmogorov Complexity Revisited “, SIAM Journal on Computing , sv. 31, n o 3,1 st 01. 2001, str. 887–905 ( ISSN 0097-5397 , DOI 10.1137 / S009753979834388X , číst online , zpřístupněno 14. července 2019 )
Eric Allender , „ When Worlds Collide: Derandomization, Lower Bound, and Kolmogorov Complexity “, of Reductions, in „proc.29thacm Symposium on Theory of Computing ,1997, str. 730–738 ( číst online , přístup k 14. července 2019 )
E. Allender , H. Buhrman, pan Koucky a D. van Melkebeek , „ Síla z náhodných řetězců “, 43. výroční sympozium IEEE o základech informatiky, 2002. Sborník. ,Listopad 2002, str. 669–678 ( DOI 10.1109 / SFCS.2002.1181992 , číst online , přistupováno 14. července 2019 )
(in) Eric Allender , Harry Buhrman a Michal Koucký : „ Co lze efektivně snížit na struny K-Random? » , STACS 2004 , Springer Berlin Heidelberg, přednáška Poznámky z informatiky,2004, str. 584-595 ( ISBN 9783540247494 , DOI 10.1007 / 978-3-540-24749-4_51 , číst online , přístup k 14. červenci 2019 )

Dodatky

Bibliografie

(fr) Gregory Chaitin Šance a složitost v matematice, hledání Ω , Flammarion, leden 2007 ( ISBN 2082105687 ) .
Ming Li a Paul Vitanyi. Úvod do Kolmogorovovy složitosti a jejích aplikací. Springer Verlag 2008 ( ISBN 978-0-387-49820-1 )

Související články