コルモゴロフ複雑性

コルモゴロフ複雑性（コルモゴロフふくざつせい、英語: Kolmogorov complexity）とは、計算機科学において有限長のデータ列の複雑さを表す指標のひとつで、出力結果がそのデータに一致するプログラムの長さの最小値として定義される。コルモゴロフ複雑度、コルモゴロフ＝チャイティン複雑性 (Kolmogorov-Chaitin complexity) とも呼ばれる。

この画像はフラクタル図形であるマンデルブロ集合の一部である。このJPEGファイルのサイズは17KB以上（約140,000ビット）ある。ところが、これと同じファイルは140,000ビットよりも遥かに小さいコンピュータ・プログラムによって作成することが出来る。従って、このJPEGファイルのコルモゴロフ複雑性は140,000よりも遥かに小さい。

コルモゴロフ複雑性の概念は一見すると単純なものであるが、チューリングの停止問題やゲーデルの不完全性定理と関連する深遠な内容をもつ。コルモゴロフ複雑性やその他の文字列やデータ構造の複雑性の計量を研究する計算機科学の分野はアルゴリズム情報理論と呼ばれており、1960 年代末にアンドレイ・コルモゴロフ、レイ・ソロモノフ、グレゴリー・チャイティンによって創始された。

定義

厳密には、ある有限長の文字列 x として表されるデータ列のある万能計算機 u におけるコルモゴロフ複雑性は以下の式で定義される:

K_{u}(x)=\min _{p:u(p)=x}\,l(p)

ここで、p は計算機 u のためのプログラムであり、u(p) はそれを実行したときに出力される文字列である。l(p) はプログラムの長さを表す。ただし、プログラムは入力をもたず、つねに決まった出力を返すようなものとする。ここで万能計算機とは万能チューリングマシンと同等の能力をもつ計算機を意味し、例えば C など通常のプログラム言語を解釈し実行するような処理系だと考えてよい。

直観的な例

ある文字列が別の文字列よりも複雑であると言うためにはどうすればよいかという問題を考えよう。例えば、同じ 60 文字の長さの 0, 1 からなる以下の 2 種類の文字列が与えられたとする。

010101010101010101010101010101010101010101010101010101010101

110010000110000111011110111011001111101001000010010101111001

これらを見比べると、直観的に前者の文字列はより簡単であって、後者の方はより複雑であると感じる。この直観を明確にするひとつの方法として、文字列を言語で説明することを考えよう。このとき前者は「01 の 30 回の繰り返し」と 11 文字で説明できる。それに対して、後者はそのような簡単な説明が与えられそうもなく、説明するには文字列そのものを含めて 60 文字以上で記す他はないように思える。

この例のように言語による記述によって短くできる文字列がある一方で、圧縮できないような文字列も存在しており、文字列の説明の長さは文字列そのものの複雑さと関係していると考えられる。このことをより形式的に取り扱うためにアルゴリズムという概念を用いて定式化されたものがコルモゴロフ複雑性である。

コルモゴロフ複雑性を定めるためには、文字列に対する形式的な記述言語をまず指定しなければならない。このような記述言語としては何かの具体的なプログラミング言語を選べばよい。あるプログラム言語 L を固定したとき、 L のプログラム p が有限長の文字列 x を出力するなら、p は x の「記述」であるということにする。

このとき特に p として x 自身を明示的に含むような自明な記述がある。例えば、上記の前者の文字列を標準出力に出力する Perl プログラムは、

print "010101010101010101010101010101010101010101010101010101010101"

のようになるだろう。このようなプログラムの長さは明らかに x の長さよりもある定数分だけ長くなる。しかし文字列に何かの構造が発見できれば、適切なアルゴリズムを用いることによってより短いプログラムを作れるかもしれない。例えば次のPerlプログラムは上と同じ文字列を出力する。

print "01" x 30

このように記述言語 L における文字列 x のあらゆる記述のうちで最小の長さをもつ記述が見出せたとするなら、その長さが L における x のコルモゴロフ複雑性となる。

基本的な性質

自明な上限

前述の例で示されたように明示的に文字列 x をプログラムに含めることができるので、すべての x に対してそのコルモゴロフ複雑性 K_u(x) は x 自体の長さ |x| を定数分以上越えることはない。すなわち、

定理： 任意の u に対して、ある定数 c が存在して、任意の x に対して、

K_{u}(x)\leq |x|+c

が成り立つ。

記述言語による相対性

定義から明らかなように、コルモゴロフ複雑性は記述言語あるいは万能計算機に依存する。しかし、ある万能計算機 u₁ から別の万能計算機 u₂ にプログラムを移植しても、コルモゴロフ複雑性はたかだか（u₁ と u₂ によって決まる）定数分しか増えない。なぜなら2つの万能計算機は、必ずもう一方の計算機をエミュレートできるからである。 u₂ 上で u₁を模倣するエミュレーションプログラム ε_1,2 を作り、その上で u₁ のためのプログラム p を動かせば、結果として u₂ の上でプログラム p を動かせたことになる。そしてこのエミュレーションプログラムはエミュレートするプログラムの大きさにかかわらずつねに一定である。従って、 u₂ 上でのコルモゴロフ複雑性はたかだか l(p) + l(ε_1,2) である。逆の場合も同様にエミュレートができるので、すなわち、

定理： 任意の万能計算機 u₁, u₂ に対し、ある定数 c_1,2 が存在して、任意の x に対し、

|K_{1}(x)-K_{2}(x)|\leq c_{1,2}.

が成り立つ。

なおコルモゴロフ複雑性の議論では、記述言語の違いによりこのようなある定数分を除いて成立するという関係が頻出する。

圧縮不能な文字列

文字列 x が K_u(x) ≧ |x| となるなら x は「圧縮不能」であるという。このような圧縮不能な文字列が存在するならどの程度存在するかを考えたい。まず、簡単な基数 (濃度) についての考察から、ある長さの文字列 x すべての中には「圧縮不能」な文字列が少なくとも 1 つは存在していることがわかる。なぜなら、長さ n のバイナリ列 (2 種類のアルファベットからなる文字列) は 2ⁿ 個存在するが、それより短いバイナリ列は長さ 0 も含めて 2ⁿ - 1 しか存在しないからである。さらに同じ理由で、長さ n 以下の 2ⁿ⁺¹ - 1 個のバイナリ列のうち、その半数より多い 2ⁿ が長さ n をもつのであるから、ある長さ以下のバイナリ列のうち圧縮不能な文字列は半数より多い。

一般に、圧縮不能の定義に自然数 c だけの余裕を入れ、K_u(x) ≧ |x| - c を満たすとした x を「c 圧縮不能」という。長さ n - c より短いバイナリ列の個数は、長さ n のバイナリ列と比べ、 (2^n-c - 1) / 2ⁿ しかないので、 c 圧縮不能な文字列は全体の 1 - 1/2^c より多い。例えば、 c = 100 ビットだけ圧縮できるような文字列は、たかだか全体の 2^-100 ∼ 10^-30 しかない。

よって、ほとんどの文字列は文字列の長さと大きく違わないコルモゴロフ複雑性しかもたないだろうと結論できる。

コルモゴロフ複雑性の計算不能性

コルモゴロフ複雑性に関する計算理論上の興味深い帰結のひとつは、コルモゴロフ複雑性が実効的に計算できないということである。

定理： K は計算可能関数ではない。

言い換えれば、任意の文字列 s を入力として整数 K(s) を出力するようなプログラムは存在しない。証明は背理法による。以下、あるプログラムを構成し、そのプログラムから出力される文字列が、そのプログラムよりも長いプログラムからでなければ出力され得ないという矛盾を導く。次のようなプログラムがあるとしよう：

  function KolmogorovComplexity(string s)

これは文字列 s を入力とし K(s) を返却する。ここで次のようなプログラムを考える。

  function GenerateComplexString(int n)
     for i = 1 to 無限大:
        for each 長さが丁度 i である string s の全集合に対して
           if KolmogorovComplexity(s) >= n
              return s
              quit

このプログラムは KolmogorovComplexity() をサブルーチンとして呼び出す。このプログラムは長さが1から無限大に至るまでのありとあらゆる文字列を調べ、コルモゴロフ複雑性が少なくとも n 以上であるような文字列を見つけたらそれを返す。従って、任意の正の整数 n について、これはコルモゴロフ複雑性が少なくとも n 以上であるような文字列を生成する。このプログラム自身は固定的な長さを持つが、その長さを U と書こう。プログラム GenerateComplexString() に対する入力は整数 n だが、この大きさは n を表すのに必要なビット数で測ることとすると、これは log₂(n) である。さて、ここで更に次のようなプログラムを考える：

  function GenerateParadoxicalString()
      return GenerateComplexString(n₀)

このプログラムは GenerateComplexString() をサブルーチンとして呼び出すが、その際 n₀ という任意の変数を引き渡す。このプログラムはコルモゴロフ複雑性が少なくとも n₀ 以上であるような文字列 s を出力する。このとき、n₀ を適切に選ぶと矛盾を導くことができる。この値を選ぶに当っては、s が GenerateParadoxicalString() というプログラムによって生成される点に着目すると良い。このプログラムの長さは、たかだか

U+\log _{2}(n_{0})+C\quad

である（C は GenerateParadoxicalString() が GenerateComplexString() を呼び出す前後の固定部分の長さを表す）。n と log₂(n) では前者の方が急速に増大することが明らかなので、ある n₀ が存在して次の関係を満たす。

U+\log _{2}(n_{0})+C<n_{0}.\quad

ところが、これは「少なくとも n₀ 以上の複雑性を持つ」ということの定義に反してしまう。何故なら K(s) の定義により、文字列 s を生成したプログラムの長さは少なくとも n₀ 以上はある筈なのに、s を生成した GenerateParadoxicalString() の長さは n₀ よりも短いからである。以上より、"KolmogorovComplexity" というプログラムは、任意の文字列について複雑性を計算することは出来ないことが示された。

この証明は背理法によるが、ここで現れる矛盾はベリーのパラドックスに似ている：「n を30字未満では表現できない最小の正の整数としよう」。他の証明方法として、K が計算不能であることを停止問題 H が計算不能であることに帰着して示すこともできる。K と H はチューリング同値である^[1]。

チャイティンの不完全性定理

殆どの文字列は、より「圧縮された」形では表現できないという意味で複雑である。しかしながら、文字列の長さがある閾値を超える場合、その文字列が複雑であることを形式的に証明することは出来ない、ということが言えてしまう。正確な定式化は以下の通り。まず、自然数を扱う特定の公理系 S を固定する。この公理系は次のことが出来る程度には強いものとする。即ち、S に含まれる式 F_A を、文字列の複雑さに関する或る主張 A に関連付けることが出来る。この際、F_Aが S の公理から証明可能なら、これに対応する主張 A も真になるとする。この「定式化」に際しては、ゲーデル数化のような人工的な符号化を用いてもよいし、適用しようとする S をもっと明快に表現するような定式化を用いても良い。

定理：次の式（をS の中で定式化したもの）を公理系 S の中で証明できるように文字列 s を取れないような、定数 L（具体的な値は公理系と記述言語にのみ依存する）が存在する。

K(s)\geq L.

圧縮不能に近い文字列は大量にあることから、殆ど全ての場合にこの式は真である筈なことに注意されたい。

この結果の証明はベリーのパラドックスに似た自己言及的な構成を用いる。以下、背理法による。この定理が偽だと仮定すると、次のことが言える。

主張(X)：任意の整数 n について、ある文字列 s が存在し、体系Sの中で式「K(s)≧n」（がSの中で定式化できると仮定して）を証明できる。

S内の形式的証明全てを実効的に枚挙する何らかの手段を見つけることができる。

  function NthProof(int n)

は入力として n を取り、適当な証明を出力する。この関数は全ての証明を枚挙する。その中には我々にとって差し当たり興味のない証明も混ざるだろう（NthProof()が枚挙する証明の中には例えば平方剰余の相互法則の証明、フェルマーの小定理の証明、フェルマーの最終定理の証明など、様々な既知の証明をS内の形式的言語に翻訳したものが現れるだろう）。この中の幾つかは K(s)≧n という形をした複雑性に関する式の証明である（s と n はS内の言語における定数）。さて、次のプログラムが存在する。

  function NthProofProvesComplexityFormula(int n)

このプログラムは n 番目の証明が式 K(s)≧L を証明しているどうかを判定する。文字列 s と整数 L はそれぞれ以下のプログラムで計算可能である：

  function StringNthProof(int n)

  function ComplexityLowerBoundNthProof(int n)

ここで次のようなプログラムを考えよう。

  function GenerateProvablyComplexString(int n)
     for i = 1 to 無限大:
        if  NthProofProvesComplexityFormula(i) and ComplexityLowerBoundNthProof(i) >= n 
           return StringNthProof(i)
           quit

任意の n について、このプログラムは形式体系S内のありとあらゆる証明を調べ上げて、K(s)≧L（但しL ≧ n ）を満たす文字列と証明を探し出そうとする。主張(X)によりこのプログラムは必ず停止する。このプログラムの長さを U としよう。このとき、ある整数 n₀ があって、U + log₂(n₀) + C < n₀ を満たす。ここで C は、次のプログラムがGenerateProvablyComplexString()を呼び出す前後の固定的な長さである。

   function GenerateProvablyParadoxicalString()
      return GenerateProvablyComplexString(n₀)
      quit

プログラム GenerateProvablyParadoxicalString() は文字列 s を出力するが、このとき L が存在して K(s)≧L（但し L ≧ n₀）を満たし、S内でこれを形式的に証明できる。特に K(s)≧n₀ は真である。ところが、s は長さが U+log₂(n₀)+C であるプログラムでも生成できるので、その複雑性は n₀ よりも小さい。これは矛盾である。よって主張(X)は成り立たないことが証明された。

同様のアイディアはチャイティンの定数の性質を証明する際にも使われている。

脚注

^ Miltersen, Peter (2005年9月29日). “Course notes for Data Compression - 2 Kolmogorov complexity Fall 2005” (PDF). University of Aarhus. 2009年7月19日閲覧。

参考文献

Ming Li, P.M.B. Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, Springer-Verlag, 1993:1997, ISBN 0387948686

[1] Miltersen, Peter (2005年9月29日). “Course notes for Data Compression - 2 Kolmogorov complexity Fall 2005” (PDF). University of Aarhus. 2009年7月19日閲覧。

[1]

コルモゴロフ複雑性

定義

直観的な例

基本的な性質

自明な上限

記述言語による相対性

圧縮不能な文字列

コルモゴロフ複雑性の計算不能性

関連する問題

データ圧縮の限界

ランダム性

チャイティンの不完全性定理

脚注

関連項目

参考文献