P≠NP 予想とは何か：多項式時間・証明書・帰着で計算の壁を測る

0. この記事の要点

• $\mathrm{P}$ は「多項式時間で答えを出せる問題」、$\mathrm{NP}$ は「答えが yes のとき、その根拠（証明書）を多項式時間で検算できる問題」のクラスです。NP の N は non-deterministic（非決定性）の頭文字であって、non-polynomial ではありません。
• $\mathrm{P} \subseteq \mathrm{NP}$ は数行で証明できます。逆向きの包含 $\mathrm{NP} \subseteq \mathrm{P}$ が成り立つかどうかが未解決で、これが P≠NP 予想です。
• 多項式時間帰着 $A \le_{\mathrm{p}} B$ は「$B$ が解ければ $A$ も解ける」を精密にした道具です。これを使うと「NP の中で最も難しい問題」＝ NP 完全問題を定義できます。SAT・3SAT・独立集合・巡回セールスマン（決定版）はすべて NP 完全です。
• NP 完全問題がひとつでも多項式時間で解ければ $\mathrm{P} = \mathrm{NP}$ が従い、NP に属するすべての問題が一斉に多項式時間で解けます。逆に $\mathrm{P} \ne \mathrm{NP}$ なら、NP 完全問題は 1 つも多項式時間では解けません。
• $\mathrm{P} = \mathrm{NP}$ なら公開鍵暗号は成立せず、組合せ最適化と（長さに上限を付けた）定理証明が自動化されます。この帰結があまりに強すぎることが、多くの研究者が $\mathrm{P} \ne \mathrm{NP}$ を予想する理由のひとつです。
• 相対化・自然証明・代数化という 3 つの「障壁」が知られており、既存の証明技法の自然な範囲では決着しないことが定理として示されています。

1. 動機 — 「解ける」と「速く解ける」の間

1930 年代にチューリングとチャーチが確立した計算可能性の理論は、「原理的に解ける問題」と「どんなアルゴリズムでも解けない問題」を分けました。しかし実務家にとって重要なのは、その内側にあるもう 1 本の線です。停止することは分かっていても、答えが返るのが宇宙の年齢より先なら、解けていないのと同じだからです。

この「もう 1 本の線」を最初にはっきり書いたのは、1956 年にゲーデルがフォン・ノイマンに宛てた手紙だと言われています。ゲーデルはそこで、「ある論理式が長さ $n$ 以下の証明を持つかどうか」を機械が判定するのに必要なステップ数 $\varphi(n)$ を問題にし、それが $n$ や $n^2$ のオーダーで済むのか、それとも本質的に指数的なのかと尋ねました。もし多項式で済むなら数学者の仕事の相当部分が機械に置き換わる、と彼は書いています。これが現在の P vs NP 問題とほぼ同じ問いです。

1960 年代に入ると、エドモンズが最大マッチングの論文で「良いアルゴリズム＝入力サイズの多項式時間で動くアルゴリズム」という基準を明示し、コバムが同様の提案を独立に行いました。多項式時間を効率性の代理指標に選ぶ理由は 2 つあります。第 1 に、多項式は合成と加算について閉じているので、「多項式時間の部品を多項式回呼ぶ」プログラムがまた多項式時間になります。第 2 に、計算モデルを取り替えても多項式時間という枠は変わりません（注意 3.2）。$O$ 記法とスケーラビリティの一般論は 計算量と O 記法 を、多項式時間アルゴリズムという枠組みそのものについては 多項式時間アルゴリズムの定義（定義 7.1）［計算量と O 記法］ を参照してください。

指数と多項式の差がどれくらい残酷かを数字で見ておきます。$n$ 個の真偽値の組合せをすべて試すと $2^n$ 通りです。$n = 100$ なら $2^{100} \approx 1.27 \times 10^{30}$ 通りで、1 秒あたり $10^9$ 通り調べられる計算機でも約 $4.0 \times 10^{13}$ 年、宇宙の年齢（およそ $1.38 \times 10^{10}$ 年）の約 2900 倍かかります。一方 $n^3$ なら $10^6$ 回、つまり 1 ミリ秒です。マシンを 1000 倍速くしても $2^n$ の側は $n$ が 10 増えるだけで元に戻ります（例 5.4［計算量と O 記法］）。指数時間の問題は「もっと速い計算機を買う」では解決しません。

巡回セールスマン問題（TSP）はこの落差の代表例です。$n$ 都市の巡回路をすべて数え上げると $(n-1)!/2$ 通りで、$n = 30$ では約 $4.4 \times 10^{30}$ 通りになります。ところが 動的計画法 の考え方（定理 3.2［動的計画法］）に基づく Held–Karp のアルゴリズムを使えば $O(n^2 2^n)$、$n = 30$ なら約 $9.7 \times 10^{11}$ 回の演算で済み、これは現実の計算機で数十分の仕事です。$10^{30}$ が $10^{12}$ になったのは大進歩ですが、$n = 100$ では $100^2 \cdot 2^{100} \approx 1.3 \times 10^{34}$ となり、やはり手が出ません。指数の底や係数を改善しても、指数であるかぎり壁は残ります。

では TSP に多項式時間アルゴリズムは存在しないのでしょうか。50 年以上探しても見つかっていませんが、「見つかっていない」と「存在しない」は別のことです。この記事の目的は、この差を数学の言葉で書き下し、「TSP が難しい」という直観を「TSP が多項式時間で解けるなら、NP に属するすべての問題が多項式時間で解ける」という定理に変えることです。

ここから先は Pro プランの内容です。

この章の続き（定義・定理・証明・例・演習）をすべて読むには Pro プランにご登録ください。無料の章は最後まで読めます。

プランを見る ログイン