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

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

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

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

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

${\ Displaystyle \ Rightarrow \ журнал P (X, Y) = \ журнал P (X) + \ журнал P (Y | X)}$

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

${\ Displaystyle К (Икс, Y) = К (Икс) + К (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, 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 ^{K (x, y)} элементов (поскольку существует не более 2 ⁿ программ длины n).

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

Ссылки

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

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

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