コルモゴロフ複雑性（コルモゴロフふくざつせい、）とは、計算機科学において有限長のデータ列の複雑さを表す指標のひとつで、出力結果がそのデータに一致するプログラムの長さの最小値として定義される。コルモゴロフ複雑度、コルモゴロフ＝チャイティン複雑性 () とも呼ばれる。コルモゴロフ複雑性の概念は一見すると単純なものであるが、チューリングの停止問題やゲーデルの不完全性定理と関連する深遠な内容をもつ。コルモゴロフ複雑性やその他の文字列やデータ構造の複雑性の計量を研究する計算機科学の分野はアルゴリズム情報理論と呼ばれており、1960 年代末にアンドレイ・コルモゴロフ、レイ・ソロモノフ、グレゴリー・チャイティンによって創始された。厳密には、ある有限長の文字列 "x" として表されるデータ列のある万能計算機 "u" におけるコルモゴロフ複雑性は以下の式で定義される:ここで、"p" は計算機 "u" のためのプログラムであり、"u"("p") はそれを実行したときに出力される文字列である。"l"("p") はプログラムの長さを表す。ただし、プログラムは入力をもたず、つねに決まった出力を返すようなものとする。 ここで万能計算機とは万能チューリングマシンと同等の能力をもつ計算機を意味し、例えば C など通常のプログラム言語を解釈し実行するような処理系だと考えてよい。ある文字列が別の文字列よりも複雑であると言うためにはどうすればよいかという問題を考えよう。 例えば、同じ 60 文字の長さの 0, 1 からなる以下の 2 種類の文字列が与えられたとする。 これらを見比べると、直観的に前者の文字列はより簡単であって、後者の方はより複雑であると感じる。 この直観を明確にするひとつの方法として、文字列を言語で説明することを考えよう。 このとき前者は「01 の 30 回の繰り返し」と 11 文字で説明できる。 それに対して、後者はそのような簡単な説明が与えられそうもなく、説明するには文字列そのものを含めて 60 文字以上で記す他はないように思える。 この例のように言語による記述によって短くできる文字列がある一方で、圧縮できないような文字列も存在しており、文字列の説明の長さは文字列そのものの複雑さと関係していると考えられる。 このことをより形式的に取り扱うためにアルゴリズムという概念を用いて定式化されたものがコルモゴロフ複雑性である。 コルモゴロフ複雑性を定めるためには、文字列に対する形式的な記述言語をまず指定しなければならない。 このような記述言語としては何かの具体的なプログラミング言語を選べばよい。 あるプログラム言語 "L" を固定したとき、 "L" のプログラム "p" が有限長の文字列 "x" を出力するなら、"p" は "x" の「記述」であるということにする。 このとき特に "p" として "x" 自身を明示的に含むような自明な記述がある。 例えば、上記の前者の文字列を標準出力に出力する Perl プログラムは、のようになるだろう。 このようなプログラムの長さは明らかに "x" の長さよりもある定数分だけ長くなる。 しかし文字列に何かの構造が発見できれば、適切なアルゴリズムを用いることによってより短いプログラムを作れるかもしれない。 例えば次のPerlプログラムは上と同じ文字列を出力する。このように記述言語 "L" における文字列 "x" のあらゆる記述のうちで最小の長さをもつ記述が見出せたとするなら、その長さが "L" における "x" のコルモゴロフ複雑性となる。前述の例で示されたように明示的に文字列 "x" をプログラムに含めることができるので、すべての "x" に対してそのコルモゴロフ複雑性 "K"("x") は "x" 自体の長さ |"x"| を定数分以上越えることはない。 すなわち、定理： 任意の "u" に対して、ある定数 "c" が存在して、任意の "x" に対して、が成り立つ。定義から明らかなように、コルモゴロフ複雑性は記述言語あるいは万能計算機に依存する。 しかし、ある万能計算機 "u" から別の万能計算機 "u" にプログラムを移植しても、コルモゴロフ複雑性はたかだか（"u" と "u" によって決まる） 定数分しか増えない。なぜなら2つの万能計算機は、必ずもう一方の計算機をエミュレートできるからである。 "u" 上で "u"を模倣するエミュレーションプログラム ε を作り、その上で "u" のためのプログラム "p" を動かせば、結果として "u" の上でプログラム "p" を動かせたことになる。 そしてこのエミュレーションプログラムはエミュレートするプログラムの大きさにかかわらずつねに一定である。 従って、 "u" 上でのコルモゴロフ複雑性はたかだか "l"("p") + "l"(ε) である。 逆の場合も同様にエミュレートができるので、すなわち、定理： 任意の万能計算機 "u

出典:wikipedia