コルモゴロフ複雑性の連鎖律

コルモゴロフ複雑性の連鎖律^{[要出典]は、}情報エントロピーの連鎖律に類似しており、次のように述べられています。

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

つまり、2 つのシーケンスXとYの組み合わせたランダム性は、 Xのランダム性と、 X がわかれば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)))}$

（正確なバージョン、KP ( x , y ) = KP ( x ) + KP ( y | x ^∗ ) + O (1)は、プレフィックス複雑度KPに対して成り立ち、ここでx ^∗はxの最短プログラムです。）

これは、 XとY を出力する最短のプログラムは、Xに最大で対数係数 を加えた場合に、X を出力する最短のプログラムとYを出力するプログラムを連結することによって得られると述べています。結果は、コルモゴロフ複雑性の相互情報量の類似物であるアルゴリズムの相互情報量が対称的であることを示唆しています。つまり、すべてのx,yに対してです。 ${\displaystyle I(x:y)=I(y:x)+O(\log K(x,y))}$

≤ の方向は明らかです。xを生成するプログラム、 x へのアクセスを与えられた y を生成するプログラム、および（ここから log 項となる）プログラムのうちの 1 つの長さを連結することによって、xとyを生成するプログラムを書くことができます。これにより、 xとyの 2 つのプログラムをどこで分離するかがわかります| x (log( K ( x , y ))がこの長さの上限です)。

≥ 方向については、⁠ ⁠となるすべてのk,lに対して、以下のいずれかが成り立つ ことを示せば十分です。${\displaystyle k+l=K(x,y)}$

${\displaystyle K(x|k,l)\leq k+O(1)}$

または

${\displaystyle K(y|x,k,l)\leq l+O(1)}$。

長さがちょうど⁠ ⁠ [したがって⁠ ⁠ ]のプログラムによって生成されるすべてのペアのリスト ( a ₁ , b ₁ ), ( a ₂ , b ₂ ), ..., ( a _e ,b _e ) を考えます。このリストは ${\displaystyle (a,b)}$${\displaystyle K(x,y)}$${\displaystyle K(a,b)\leq K(x,y)}$

• ⁠ ⁠ の${\displaystyle (x,y)}$ペアが含まれています、
• kとlが与えられれば列挙できる（長さ⁠ ⁠のすべてのプログラムを並列に実行することによって）。${\displaystyle K(x,y)}$
• 最大で 2 ^{K ( x , y )個の要素を持ちます (長さ}nのプログラムは最大で 2 ^{n 個}あるため)。

まず、x が最初の要素として2 ^l回未満しか出現しないとします。( a ₁、b ₁ )、 ( a ₂、b ₂ )、... を列挙し、次にペアのサブリストから⁠ ⁠を選択することで、 x、k、lが与えられた場合に y を指定できます。仮定により、このサブリスト内の⁠ ⁠のインデックスは2 ^l未満であるため、長さ ⁠ ⁠ のx 、k、lが与えられた場合にyのプログラムが存在します。ここで、x が最初の要素として少なくとも2 ^l回出現するとします。これは、最大で2 ^{K ( x、y )−l} = 2 ^kの異なる文字列に対して発生する可能性があります。これらの文字列はk、l が与えられた場合に列挙できるため、この列挙内のインデックスによってx を指定できます。 xに対応するプログラムのサイズは⁠ ⁠です。定理が証明されました。 ${\displaystyle (x,y)}$${\displaystyle (x,b)}$${\displaystyle (x,y)}$${\displaystyle l+O(1)}$${\displaystyle k+O(1)}$

• Li, Ming; Vitányi, Paul (1997年2月)。コルモゴロフ複雑性とその応用への入門。ニューヨーク: Springer- Verlag。ISBN 0-387-94868-6。

• Kolmogorov, A. (1968). 「情報理論と確率理論の論理的基礎」. IEEE Transactions on Information Theory . 14 (5). 電気電子技術者協会 (IEEE): 662–664. doi :10.1109/tit.1968.1054210. ISSN  0018-9448. S2CID  11402549.

• Zvonkin, AK; Levin, LA (1970-12-31). 「有限オブジェクトの複雑性とアルゴリズム理論による情報とランダム性の概念の発展」.ロシア数学概論. 25 (6). IOP 出版: 83–124. Bibcode :1970RuMaS..25...83Z. doi :10.1070/rm1970v025n06abeh001269. ISSN  0036-0279. S2CID  250850390.