コロモゴロフ複雑性の「不変性」

【コロモゴロフ複雑性の「不変性」】

コロモゴロフ複雑性 $𝐾_𝜑 (𝑦)$ の定義：「yを出力するプログラムpの最小の長さ」の問題の一つは、この $𝐾_𝜑 (𝑦)$ が、プログラムを実行する𝜑に強く依存していることです。

　　　　　　 $𝐾_𝜑 (𝑦)$ = min ⁡{ |𝑝| : 𝜑(𝑝)=𝑦 }

事実、プログラムが Pythonで書かれているか、Javaで書かれているか、Assemblerで書かれているか, …. で、同じyを出力するプログラムの長さは、それぞれ違います。

ただ、任意の𝜑に対して、次の不等式を満たすVが存在することを示すことが出来ます。

$𝐾_𝑉 (𝑦) ≤ 𝐾_𝜑 (𝑦) + 𝑐$

ここで、cは定数です。（証明は、後に回します）

すべての𝜑に対して、この不等式を満たすVと定数cが存在することを、コロモゴロフ複雑性の「不変性定理」と呼びます。

この不等式を満たすVを「最適な」Vと呼ぶことにしましょう。

「不変性定理」は、 𝜑がいろいろ変わっても、

$𝐾_𝜑$ の(正確に言えば

$𝐾_𝜑 (𝑦) + 𝑐$ の)最小値𝐾_𝑉を与える「最適な」Vが存在することを主張しています。

「不変性定理」で定義される「最適な」 V を使って、新しいコロモゴロフ複雑性 K(y)を次のように定義できます。

$𝐾(𝑦)≡𝐾_𝑉 (𝑦)$

この𝐾(𝑦)が、新しいコロモゴロフ複雑性の定義になります。

$𝐾(𝑦)≡𝐾_𝑉 (𝑦) ≤ 𝐾_𝜑 (𝑦) + 𝑐$

ですので、𝐾(𝑦)は、

$𝐾_𝜑 (𝑦)$ たちの取る値の最小値です。

もし、𝑉と𝑉 'が共に「最適」であるなら、

$|𝐾_𝑉 (𝑦) − 𝐾_{𝑉′'} (𝑦)| ≤ 𝑐$

が成り立ちます。

コロモゴロフは、論文”Three approaches to the quantitative definition of information” 1965 の中でこの定数について、次のように述べています。

「もちろん、特定の関数Vを考えることで、この定数cに関連した非決定性を避けることはできる。しかし、あからさまな恣意性抜きに、そうしたことができるかは疑わしい。

しかし、合理的な異なる「最適」な関数が、「複雑性の評価」に導き、それが数万ビットではなく、数百ビットに収斂すると想定しなくてはならない。

よって、例えば、「戦争と平和」のテキストの複雑性のような量は、ユニークなものとして定義されると推測することができる。」

ショートムービーお楽しみください。

スライドのpdfは、次からアクセスできます。

過去・現在・未来