Řetězové pravidlo pro Kolmogorovovu složitost - Chain rule for Kolmogorov complexity

Tento článek obsahuje a seznam doporučení, související čtení nebo externí odkazy, ale jeho zdroje zůstávají nejasné, protože mu chybí vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Červenec 2014) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Řetězové pravidlo^{[Citace je zapotřebí ]} pro Kolmogorovova složitost je obdobou řetězového pravidla pro informační entropie, které státy:

${ displaystyle H (X, Y) = H (X) + H (Y | X)}$

To znamená kombinované náhodnost dvou sekvencí X a Y je součet náhodnosti X plus jakákoli náhodnost je ponechána Y jakmile to víme XTo bezprostředně vyplývá z definic podmiňovací způsob a společná entropie a skutečnost z teorie pravděpodobnosti že společná pravděpodobnost je produktem okrajový a podmíněná pravděpodobnost:

${ displaystyle P (X, Y) = P (X) P (Y | X)}$

${ displaystyle Rightarrow log P (X, Y) = log P (X) + log P (Y | X)}$

Ekvivalentní prohlášení pro Kolmogorovovu složitost neplatí přesně; je to pravda jen do a logaritmický období:

${ displaystyle K (x, y) = K (x) + K (y | x) + O ( log (K (x, y)))}$

(Přesná verze, KP(X, y) = KP(X) + KP(y|X*) + O (1), platí pro složitost předpony KP, kde X* je nejkratší program pro X.)

Uvádí, že nejkratší tisk programu X a Y se získá zřetězením nejkratšího tisku programu X s tiskem programu Y daný X, Plus nejvíce logaritmický faktor. Výsledky to naznačují algoritmické vzájemné informace, analog vzájemné informace pro Kolmogorovovu složitost je symetrický: I (x: y) = I (y: x) + O (log K (x, y)) pro všechny x, y.

Důkaz

Směr ≤ je zřejmý: můžeme napsat program, který se má vyrobit X a y zřetězením programu výroby X, program na výrobu y daný přístup k Xa (odtud logický výraz) délka jednoho z programů, takže víme, kde oddělit dva programy pro X a y|X (log (K.(X, y)) horní hranice této délky).

Pro směr ≥ stačí ukázat, že pro všechna k, l taková, že k + l = K (x, y) máme buď

K (x | k, l) ≤ k + O (1)

nebo

K (y | x, k, l) ≤ l + O (1).

Zvažte seznam (A₁, b₁), (a₂, b₂), ..., (a_E, b_E) všech párů (a, b) produkované programy délky přesně K (x, y) [tedy K (a, b) ≤ K (x, y)]. Všimněte si, že tento seznam

• obsahuje pár (x, y),
• může být vyjmenovaný daný k a l (spuštěním všech programů délky K (x, y) paralelně),
• má nanejvýš 2^{K (x, y)} prvky (protože tam jsou maximálně 2ⁿ programy délky n).

Nejprve předpokládejme, že X se objeví méně než 2^l krát jako první prvek. Můžeme specifikovat y daný x, k, l výčtem (A₁, b₁), (a₂, b₂), ... a poté vyberte (x, y) v dílčím seznamu párů (x, b). Předpokládá se, že index (x, y) v tomto podřízeném seznamu je méně než 2^l a proto existuje program pro y daný x, k, l délky l + O (1).Předpokládejme, že X se objeví alespoň 2^l krát jako první prvek. To se může stát maximálně 2^{K (x, y) -l} = 2^k různé řetězce. Tyto řetězce lze vyjmenovat k, l a tudíž X lze určit jeho indexem v tomto výčtu. Odpovídající program pro X má velikost k + O (1). Věta prokázána.

Reference

• Li, Ming; Vitányi, Paul (únor 1997). Úvod do Kolmogorovovy složitosti a jejích aplikací. New York: Springer-Verlag. ISBN  0-387-94868-6.

• Kolmogorov, A. (1968). "Logický základ pro teorii informací a teorii pravděpodobnosti". Transakce IEEE na teorii informací. Institute of Electrical and Electronics Engineers (IEEE). 14 (5): 662–664. doi:10.1109 / tit.1968.1054210. ISSN  0018-9448.

• Zvonkin, AK; Levin, LA (1970-12-31). "Složitost konečných objektů a vývoj pojmů informace a náhodnost pomocí teorie algoritmů". Ruské matematické průzkumy. Publikování IOP. 25 (6): 83–124. doi:10.1070 / rm1970v025n06abeh001269. ISSN  0036-0279.