Цепное правило для сложности Колмогорова - Chain rule for Kolmogorov complexity

Цепное правило^{[нужна цитата ]} для Колмогоровская сложность является аналогом цепного правила для информационная энтропия, в котором говорится:

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

То есть комбинированный случайность двух последовательностей Икс и Y это сумма случайности Икс плюс любая случайность, оставшаяся в Y как только мы узнаем ИксЭто сразу следует из определений условный и совместная энтропия, и факт из теория вероятности что совместная вероятность продукт маргинальный и условная возможность:

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

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

Эквивалентное утверждение для колмогоровской сложности в точности не выполняется; это правда только до логарифмический срок:

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

(Точная версия, КП(Икс, у) = КП(Икс) + КП(у|Икс*) + O (1), выполняется для префиксной сложности КП, где Икс* это самая короткая программа для Икс.)

В нем говорится, что самая короткая программа печати Икс и Y получается путем объединения кратчайшей программы печати Икс с программной печатью Y данный Икс, плюс в большинстве логарифмический коэффициент. Из результатов следует, что алгоритмическая взаимная информация, аналог взаимной информации для колмогоровской сложности симметричен: I (x: y) = I (y: x) + O (журнал K (x, y)) для всех х, у.

Доказательство

Направление ≤ очевидно: мы можем написать программу для производства Икс и у путем объединения программы для создания Икс, программа для производства у дан доступ к Икс, и (отсюда термин журнала) длина одной из программ, чтобы мы знали, где разделить две программы для Икс и у|Икс (бревно(K(Икс, у)) ограничивает эту длину сверху).

Для направления ≥ достаточно показать, что для всех k, l таких, что k + l = K (x, y), выполняется либо

К (х | к, l) ≤ k + O (1)

или

К (у | х, k, l) ≤ l + O (1).

Рассмотрим список (а₁, б₁), (а₂, б₂), ..., (а_е, б_е) всех пар (а, б) производится программами длины точно К (х, у) [следовательно, K (a, b) ≤ K (x, y)]. Обратите внимание, что этот список

• содержит пару (х, у),
• может быть перечисленный данный k и л (запустив все программы длины К (х, у) в параллели),
• имеет самое большее 2^{К (х, у)} элементов (потому что их не более 2^п программы длины n).

Сначала предположим, что Икс кажется меньше чем 2^л раз в качестве первого элемента. Мы можем указать у данный х, к, л перечисляя (а₁, б₁), (а₂, б₂), ... а затем выбрав (х, у) в подсписке пар (х, б). По предположению, индекс (х, у) в этом подсписке меньше чем 2^л а значит, есть программа для у данный х, к, л длины л + О (1).Теперь предположим, что Икс появляется по крайней мере 2^л раз в качестве первого элемента. Это может произойти максимум 2^{К (х, у) -l} = 2^k разные струны. Эти строки можно перечислить с учетом к, л и, следовательно Икс может быть указан его индексом в этом перечислении. Соответствующая программа для Икс имеет размер к + О (1). Теорема доказана.

использованная литература

• Ли, Мин; Витани, Пол (февраль 1997 г.). Введение в колмогоровскую сложность и ее приложения. Нью-Йорк: Springer-Verlag. ISBN  0-387-94868-6.

• Колмогоров, А. (1968). «Логические основы теории информации и теории вероятностей». IEEE Transactions по теории информации. Институт инженеров по электротехнике и радиоэлектронике (IEEE). 14 (5): 662–664. Дои:10.1109 / tit.1968.1054210. ISSN  0018-9448.

• Звонкин А К; Левин, Л. А (1970-12-31). «Сложность конечных объектов и развитие понятий информации и случайности средствами теории алгоритмов». Российские математические обзоры. IOP Publishing. 25 (6): 83–124. Дои:10.1070 / rm1970v025n06abeh001269. ISSN  0036-0279.