複雑さについて（６） 複雑さと計算量の理論

先の投稿で、次の二つの文字列を例に挙げて、それを出力するプログラムの大きさを示して、文字列mは、文字列nより複雑だろうと書いた。

　n= "111111111111111111111111111"
　m="618970019642690137449562111"

見かけ上は、nには明確なパターンがあって、mにはそうしたパターンが見当たらないというようなことも匂わせた。

ところが、これは、僕の引っ掛けなのだ。

mは、明確な特徴を持った数だ。mは、10番目のメルセンヌ素数である。だから、n番目のメルセンヌ素数を返す関数を M(n) とし、n個の1が並んだ数字を返す関数をL(n)とすれば、先の n, m を値として返すプログラムは、次のように書ける。

　 n : print L(27)
　 m : print M(10)

二つのプログラムの長さは11文字で同じ長さだ。だから、n, ｍ のコルモゴロフ複雑性は、同じだと言えることになる。

でも、この立論は、どこか怪しい。

コルモゴロフの複雑性は、プログラムを記述する系にディペンドする。ある計算システムで、任意のnに対して、関数L(n)と関数M(n)が、瞬時に答えを返してくれるなら、先の立論は正しい。

計算量の理論では、どう計算しているのかわからないブラックボックスなのだが、問いかけに、すぐに「正しい」答えを返してくれるものを想定することがある。それを「オラクル (Oracle)」と呼ぶ。文字どおり「神託」である。あの、データベースの会社の名前も、同じ神話から取られている。

オラクルの存在を仮定するのは、なんだか納得いかないと思う人も多いだろうが、こうした仮定によって、理論の見通しが良くなることがある。

先の怪しい立論は、次のように言い換えられる。

「n番目のメルセンヌ素数を返す関数K(n)が、オラクルとして与えられる計算系では、先の二つの数字 n, m のコルモゴロフ複雑性は等しくなる。」

なんか、少しはもっともらしい主張になっていそうな気もする。でも、これで満足する人はいないだろう。なんかおかしい。

この直感は、正しいのだ。

オラクルとしてではなく、具体的に、関数 L(n)とM(n)の複雑さを考えてみれば、次のことがわかる。

関数L(n)は、nが大きくなるにつれ、nに比例して計算時間が長くなる。ところが、K(n)の計算に必要な時間は、nに比例して大きくなるわけではない。それでは、n^2, n^3, n^4, n^5 , ..... に比例するのだろうか？　そのどちらでもないだろう。こうした、nの何乗かの多項式に比例する計算時間で計算可能なものを、「多項式時間で計算可能」という。L(n)は、多項式時間で計算可能な関数だ。ただ、M(n)は、もっと複雑だ。

メルセンヌ素数は、素数pに対して、2^p - 1の形をした素数のことだ。たとえ、k番目の素数が、多項式時間 p(k)で計算可能だとしても（これが正しい仮定なのか、僕は、正確なことは知らないのだが）、n番目のメルセンヌ素数を見つけるためには、最低でも、2^p(k)の計算の総当たりが必要になる。 M(n)は、多項式時間では計算できない。

（最後に、拍子抜けする話で申し訳ないが、僕は、M(n)が、多項式時間で計算できないという証明を知っているわけではない。僕が、思いつく限りの方法（単なる総当たりだ）では、できそうにないということを言っているだけだ。素数の不思議な性質が解明されて、メルセンヌ素数の系列が、不思議な関係式を満たすことが発見されることがあるのかもしれない。）

たとえ、そうだとしても、次のことは言えるはずだ。

多項式時間で計算できない数は、多項式時間で計算できる数より、複雑であると。