複雑性理論と人工知能技術（７） 数学とNP問題

「数学とNP問題」というのは、少し奇妙なタイトルかもしれない。

というのも、PやNPといったクラスを扱う「複雑性理論」自身が、数学の一分野だからである。正確にいうと、複雑性理論は、数学理論であると同時に、現在では、物理理論の一部でもある（もちろん、計算機科学の一分野でもある）。

そのためには、BQP(量子チューリングマシンで「多項式時間」で計算可能なクラス)が、現在の複雑性の理論では重要なクラスになっていることを説明しなければならないのだが、それについては、ショアのアルゴリズムを紹介した後で述べようと思う。

ここでは、数学理論としての複雑性の理論に、問題を限ってみよう。

NPクラスの説明によく用いられるのは、素因数への分解問題である。ある自然数Nを「多項式時間」で素因数に分解するアルゴリズムは、現在では、まだ見つかっていない。（多分、そんな多項式時間アルゴリズムは見つからないだろうと感じている人が多いのだが、かといって、そのことが確定しているわけではない。）

一般の数Nではなく、条件を緩めて、Nは二つの素数の積であることがわかっていたとしても、Nが大きな数になると、Nを素因数に分解すること、すなわち、N=pqであるような二つの素数 p, q を見つけることは、極めて難しくなる。

ただ、N, p, q が具体的に与えられているなら、「Nは、素数pと素数qに、素因数分解される」という主張は、簡単に検証できる。pとqを掛けて、その結果がNに等しいことを示せばいいのだから。掛け算は、もちろん簡単な計算で、多項式時間で終わる。

こうした、その問題を解くのが「多項式時間」で終わるかどうかはわからなくても、具体的な値で与えられたその問題の「答え」と言われるものが、本当に「正しい答え」であるかどうかを「多項式時間」でチェックできる問題のクラスを、NPという。素因数分解問題は、NP問題である。

（ちなみに、「答え」（なるもの）が与えられた時、それが「間違った答え」であるかどうかを「多項式時間」でチェックできる問題のクラスを、 co-NP問題という。素因数分解問題は、co-NP問題でもある。）

こうしたことや、NP問題である素因数分解問題に現れる「難しさ」と「易しさ」の「非対称性」が、現在の公開キー暗号の基礎になっていることは、多くの人が既に知っていることかもしれない。

次に述べることは、冒頭のタイトルに関係するが、少し、別のことである。

数学の問題Xがあったとしよう。問題Xを「解く」ということは、基本的には、ある形式的体系Tを選んで、その中で、Xの「証明」Sを、「数学的に」与えることである。

でも、問題Xの証明S（だと、当人が主張しているもの）が、正しい保証はない。世の中には、「間違った証明」が山ほどある。天才Wilesにしろ天才Voevodskyにしろ、自分が「間違った証明」を論文として公開したことがあることを認めているくらいだ。

それでは、ある問題Xのある証明Sが、「正しい」ことは、どのように検証できるのか？　あるいは、もっと原理的に考えて、それが「検証可能」であるという主張には、どのような前提が潜んでいるのか？　

一つの考え方は、数学の証明は、「多項式時間」で「検証可能」でなければならないと考えることだ。（今の僕は、それが正しいと感じているのだが。）

ただ、こうした考えに立って、数学の証明の「正しさ」が、多項式時間で「検証可能」だということは、数学の証明可能な問題全体が、NPクラスに属するということにならないか？

な、わけはない。（とも、思うのだが。）

次回以降で、僕が感じている「違和感」の正体を、もう少し詳しく考えたいと思う。

僕の興味は、人間と機械の認識能力の階層性（感覚・運動的外界の把握の階層、言語能力による世界把握の階層、数学的認識能力による宇宙の把握の階層）と、それぞれの階層の認識能力の「限界」にある。

言語能力が、クラスPに属するだろうということは、前に書いた。数学的能力が、全体としてクラスNPもどきの構造をしているように見えるのは、面白いことだ。それは、二つの能力が、別の階層に属することをし