Цепное правило для колмогоровской сложности.

Правило цепочки для Колмогорова сложность является аналогом цепного правила для информационной энтропии , которое гласит:

$H(X,Y)=H(X)+H(Y|X)$

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

$P(X,Y)=P(X)P(Y|X)$

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

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

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

(Точная версия: KP ( x , y ) = KP ( x ) + KP ( y | x *) + O(1),справедливо для префиксной сложности KP , где x* — кратчайшая программа для x .)

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

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

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

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

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

или

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

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

• содержит пару (x,y) ,
• можно перечислить по заданным k и l запуска всех программ длины K(x,y) ), (путем параллельного
• имеет не более 2 ^К(х,у) элементов (поскольку существует не более 2 ^н программы длины n).

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

Ссылки

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

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

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