P 対 NP

アルゴリズムが "効率的である" ための最低条件は、実行時間が入力サイズの多項式で抑えられることです。つまり入力サイズを $n$ としたときにある定数 $c$ が存在して、実行時間が $O(n^{c})$ となるということです¹。研究者達は全ての問題が高速に解けるわけではないことに早くから気付いていましたが、どの問題が早く解けてどの問題がそうでないのかを見極めるのに苦労していました。NP 困難 (NP-hard) と呼ばれる問題は誰もが多項式時間で解けないと信じているものの、実行時間の下限が超多項式的になることは誰も証明できていません。

判定問題 (decision problem) とは出力が一つの真偽値 ($\textsc{Yes}$ か $\textsc{No}$) であるような問題のことです。判定問題のクラスを三つ定義します:

P は多項式時間で解ける判定問題からなる集合です。直感的には、$P$ は高速に解ける判定問題の集合です。
NP は「もし答えが $\textsc{Yes}$ ならば、そのことを多項式時間で確認できる証明 (proof) が存在する」という特徴を持つ問題の集合です。直感的には、NP は答えが $\textsc{Yes}$ ならばそれを高速に検証できる判定問題の集合です。
co-NP は NP の逆です。co-NP に属する問題の答えが No ならば、多項式時間でそのことを検証できる証明が存在します。

例として、回路充足問題が NP に属するかどうかを考えてみます。もし回路が充足可能ならば、その回路を充足させる任意の $m$ ビットの入力を受け取って実際に回路を評価することで、充足可能性を多項式時間で確認できます。したがってこのような入力が証明となるので、回路充足問題は NP に属します。回路充足問題は P にも co-NP にも属さないと広く信じられていますが、本当のところは誰にもわかりません。

P に属する全ての判定問題は NP にも属します。なぜならもし問題が P に属しているなら、$\textsc{Yes}$ という答えは最初から問題を解くことで多項式時間で確認できるからです！同様の理由で P に属する全ての問題は co-NP にも属します。

科学、いや情報科学、いや理論情報科学における未解決問題の中で最も重要な問題を一つあげるとすれば、それは複雑性クラス P と NP が本当に異なっているのかという問題です。ほとんどの人にとって P $\neq$ NP は直感的に明らかです。アルゴリズムとデータ構造に関する講義で課題や試験に取り組んだことがあるなら、たとえ後から見れば簡単に解ける問題であったとしても、初見のアルゴリズムの問題を解くのは難しいと分かっているでしょう (分かっていることを願います)。また問題をゼロから解くことが、一つの解答が正しいかをチェックすることより難しいのは完全に明らかです。"P $\neq$ NP" という命題を自然法則として受け入れても何ら不都合は生じないでしょう ――実際多くのアルゴリズム設計者は受け入れています。つまり、P $\neq$ NP が Maxwell 方程式や相対性理論、あるいは太陽が明日昇ることと同じように証拠によって支えられていて、数学的には証明されていないということです。

一方でもし数学的に厳密になるなら、どうやって P $\neq$ NP を証明すべきかさえ誰にも分かっていないということを認めなければなりません。実は、証明に向けた進展は何十年にもわたってほとんどあるいは全くありません²。クレイ数学研究所は P 対 NP 問題を七つのミレニアム懸賞問題の一つとしており、解答を示した人物に対する $1,000,000 の賞金を用意しています。そしてこの問題を解こうして魂を (とまではいかなくても、少なくとも正気を) 失ってしまった人もいます。

複雑性クラス NP と co-NP が異なるのかというより細かい問題もまた未解決です。$\textsc{Yes}$ という答えを高速に検証できるからといって $\textsc{No}$ の答えも高速に検証できるとは限らないということです。例えば現在分かっている限りでは、回路が充足できないことに対する短い証明は存在しません。一般的には NP $\neq$ co-NP と信じられていますが、この命題もどうやって証明すべきかは誰にも分かりません。

この意味の「効率的である」という概念は 1965 年に Alan Cobham (アラン・コブハム) によって、同じく 1965 年に Jack Edmonds (ジャック・エドモンズ) によって、1966 年に Michael Rabin (マイケル・レビン) によってそれぞれ独立に提唱されました。ただし、Kurt Gödel (クルト・ゲーデル)、John Nash (ジョン・ナッシュ)、John von Neumann (ジョン・フォン・ノイマン) も同じ概念についての考察を十年以上前に行っています。^[return]
おそらく最も重要な進展は barrier result の形をとるものでしょう。この結果からは、ある条件を満たすどんな証明手段も失敗する運命にあるということが分かります。本当にそのままの意味で、P $\neq$ NP をどうすれば証明できるかは誰にも分からないだけではなく、ある種の方法を使ったときにはどうやっても P $\neq$ NP が証明できないことが証明されているのです！^[return]