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

0. この記事の要点

パズルの答えを自力で見つけるのは大変でも、誰かが答えを持ってきたときに「合っているか」を確かめるのは簡単なことがあります。この記事は、この「探す大変さ」と「確かめる手軽さ」の差が本質的なものなのか、という未解決の問いを扱います。読み終えると、P と NP という 2 つの問題の集まりの違い、ある問題が「最も難しい」と言える理由、そしてこの問いが暗号や最適化にどう関わるかを説明できるようになります。

• $\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 つの「障壁」が知られており、既存の証明技法の自然な範囲では決着しないことが定理として示されています。

この記事で使う事前知識

• 多項式時間: 入力の長さを $n$ として、計算時間が $n^2$ や $n^3$ のような多項式で抑えられること。→ 多項式時間アルゴリズム
• 指数時間: $2^n$ のように、$n$ が増えると爆発的に増える計算時間のこと。多項式時間と対比されます。
• 動的計画法: 部分問題の答えを使い回して、指数時間を多項式時間に落とす設計法。→ 動的計画法
• チューリング機械: 「手順に従って計算する」ことを数学的に表した模型。この記事では、多項式時間で動く計算機の代表として使います。
• 対偶: 「A ならば B」と「B でないならば A でない」は同値である、という論理の基本。

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 に属するすべての問題が多項式時間で解ける」という定理に変えることです。

2. 準備 — 問題を「言語」として書き直す

計算量を測るには、まず「問題」を数学的対象として固定する必要があります。標準的なやり方は、判定結果が yes/no の問題（決定問題）だけを扱い、それを文字列の集合と同一視することです。

定義 2.1（決定問題と言語）↗

アルファベットを $\Sigma = \{0, 1\}$ とし、$\Sigma^{*}$ で有限長のビット列全体を表します。$\Sigma^{*}$ の部分集合 $L$ を言語と呼びます。決定問題とは、入力 $x \in \Sigma^{*}$ に対して「$x \in L$ か」を答える問題のことであり、決定問題と言語を同一視します。数学的対象 $O$（グラフ、論理式、整数の列など）をビット列に符号化したものを $\langle O \rangle$ と書きます。入力サイズ $n$ とは、入力ビット列の長さ $|x|$ のことです。

注意 2.2

符号化の細部は普通は問題になりません。グラフを隣接行列で書くか隣接リストで書くかは互いに多項式時間で変換できるので、「多項式時間で解ける」という性質は変わらないからです。ただし例外が 1 つあります。整数を単進法（$k$ を $k$ 個の $1$）で書くことは禁じます。単進法は入力サイズを指数的に水増しし、指数時間のアルゴリズムを多項式時間に見せかけてしまうからです。整数は必ず 2 進法で符号化し、値 $k$ の入力サイズは $\lceil \log_2 (k+1) \rceil$ ビットとします。この約束は演習の部分和問題で効いてきます。

決定問題に限るのは一見不自由ですが、最適化問題は閾値を付けて決定問題に翻訳できます。「最短の巡回路の長さを求めよ」は「長さ $k$ 以下の巡回路が存在するか」という決定問題の族に置き換えられ、後者が多項式時間で解ければ二分探索で前者も多項式時間で解けます（命題 7.1 の後で詳しく述べます）。決定問題の難しさを調べれば最適化問題の難しさも分かる、ということです。

3. クラス P — 多項式時間で答えを出せる問題

定義 3.1（クラス P）↗

言語 $L \subseteq \Sigma^{*}$ が $\mathrm{P}$ に属するとは、決定性チューリング機械 $M$ と多項式 $p$ が存在して、次の 2 条件がともに成り立つことをいいます。

1. すべての入力 $x \in \Sigma^{*}$ に対し、$M$ は高々 $p(|x|)$ ステップで停止する。
2. すべての $x \in \Sigma^{*}$ に対し、$M$ が $x$ を受理することと $x \in L$ であることが同値である。

このような $L$ の全体を $\mathrm{P}$ と書きます。

条件 1 が「すべての入力に対して」であることに注意してください。平均的に速いだけでは足りず、最悪の入力でも多項式時間で止まることを要求します。

注意 3.2

定義 3.1 はチューリング機械で書いてありますが、$\mathrm{P}$ の中身は計算モデルに依存しません。1 テープ機械は多テープ機械を高々 2 乗のオーバーヘッドで、RAM モデルも多項式のオーバーヘッドで模倣でき、多項式の合成はまた多項式だからです。一方「多項式時間＝実際に効率的」という読み替え（コバム–エドモンズのテーゼ）は経験則であって定理ではありません。$n^{100}$ 時間のアルゴリズムは実用になりませんし、指数時間でも入力が小さければ十分使えます。それでも $\mathrm{P}$ が理論の基本単位に選ばれるのは、このモデル非依存性と閉包性のためです。

例 3.3（P に属する問題）

次の問題はすべて $\mathrm{P}$ に属します。括弧内は代表的な計算量です。

• ソート済みかどうかの判定、比較ソート（$O(n \log n)$、定理 4.2［ソートアルゴリズム］）。ソートアルゴリズム を参照してください。
• グラフの連結性、幅優先探索・深さ優先探索（$O(\lvert V \rvert + \lvert E \rvert)$、命題 3.3［グラフアルゴリズム］）、単一始点最短経路（ダイクストラ法で $O(\lvert E \rvert \log \lvert V \rvert)$、命題 5.4［グラフアルゴリズム］）、最大流、二部グラフの最大マッチング。グラフアルゴリズム を参照してください。
• 線形計画法の実行可能性判定。単体法は最悪指数時間ですが、ハチヤンの楕円体法が 1979 年に多項式時間であることを示しました。
• 素数判定。「整数 $N$ は素数か」は入力サイズ $n = \lceil \log_2 N \rceil$ の多項式時間で解けます（Agrawal–Kayal–Saxena, 2004）。試し割りは $\sqrt{N} = 2^{n/2}$ 回の割り算を要するので多項式時間ではない点に注意してください。

素数判定は、$\mathrm{P}$ への所属が自明でない例です。この問題が $\mathrm{NP} \cap \mathrm{coNP}$ に属することは 1970 年代から知られていましたが、$\mathrm{P}$ に属すると証明されたのは 2002 年でした。「まだ多項式時間アルゴリズムが見つかっていない」ことは「存在しない」ことの証拠になりません。

4. クラス NP — 検算の計算量

TSP の巡回路を「見つける」のは大変ですが、誰かが巡回路を持ってきたときにそれが本当に長さ $k$ 以下かを「確かめる」のは簡単です。都市の並びに沿って重みを足して $k$ と比べるだけだからです。この非対称性、すなわち発見と検算の計算量の差を切り出したものが $\mathrm{NP}$ です。

次の定義の読み方を先に述べておきます。$x$ は問題の入力（たとえば TSP の都市と重みの表）、$y$ は「答えが yes だという根拠」（たとえば巡回路そのもの）、$V$ はその根拠を検算する手順です。式は「$x$ が yes であることと、短い根拠 $y$ で検算に通るものが存在することは同じ」と読みます。

探す側と検算する側の対比（SAT で n 個の変数の場合）

定義 4.1（クラス NP（検証器による定義））↗

言語 $L \subseteq \Sigma^{*}$ が $\mathrm{NP}$ に属するとは、多項式 $p$ と、多項式時間で動く決定性チューリング機械 $V$（検証器と呼びます）が存在して、すべての $x \in \Sigma^{*}$ に対して

$$x \in L \iff \exists y \in \Sigma^{*} \ \bigl[\, |y| \le p(|x|) \ \text{かつ} \ V(x, y) = 1 \,\bigr]$$

が成り立つことをいいます。この $y$ を $x$ に対する証明書（certificate、witness）と呼びます。ここで「$V$ が多項式時間」とは、$V$ が入力 $(x, y)$ に対して $|x| + |y|$ の多項式時間で停止することを意味します。

定義の 3 つの要素をそれぞれ確認してください。第 1 に、証明書は yes の側にしか要求されません。$x \notin L$ のときは、どんな $y$ を持ってきても $V(x,y) = 0$ になることが求められます。第 2 に、証明書の長さに多項式の上限があります。この制限がないと、答えそのものを長々と書き下したものを証明書にできてしまい、定義が無意味になります。第 3 に、検証は決定性の多項式時間です。$V$ は $y$ を推測してはならず、渡された $y$ を検算するだけです。

注意 4.2

$\mathrm{NP}$ の名前は「非決定性多項式時間（Non-deterministic Polynomial time）」に由来します。非決定性チューリング機械とは、各ステップで複数の遷移先から任意に 1 つを選べる機械で、「ある選び方で受理状態に達するなら受理」と定めます。$L$ が多項式時間の非決定性機械で受理されることと、定義 4.1 の意味で $L \in \mathrm{NP}$ であることは同値です。実際、非決定性機械の各ステップでの選択肢を並べたものが証明書にほかならず、逆に証明書を非決定的に推測してから $V$ を走らせればよいからです。NP は「非多項式時間（non-polynomial）」の略ではありません。 この誤解は非常に多いので注意してください。

定義 4.3（充足可能性問題 SAT と 3SAT）↗

命題変数 $x_1, \ldots, x_n$ に対し、$x_i$ または $\lnot x_i$ の形の式をリテラル、リテラルの論理和 $(\ell_1 \lor \cdots \lor \ell_k)$ を節、節の論理積 $C_1 \land \cdots \land C_m$ を CNF 論理式（連言標準形）といいます。真理値割当 $\alpha : \{x_1,\ldots,x_n\} \to \{\text{真}, \text{偽}\}$ が CNF 論理式 $\varphi$ を真にするとき、$\alpha$ は $\varphi$ を充足するといい、そのような $\alpha$ が存在する $\varphi$ を充足可能といいます。

$$\mathrm{SAT} = \{\, \langle \varphi \rangle : \varphi \ \text{は充足可能な CNF 論理式} \,\}$$

とおきます。さらに、すべての節がちょうど 3 個のリテラルからなる CNF 論理式に制限したものを $\mathrm{3SAT}$ と書きます。

例 4.4（SAT の証明書を実際に検算する）

$$\varphi = (x_1 \lor \lnot x_2 \lor x_3) \land (\lnot x_1 \lor x_2) \land (\lnot x_2 \lor \lnot x_3) \land (x_1 \lor x_3)$$

に対し、証明書として割当 $\alpha = (x_1, x_2, x_3) = (\text{真}, \text{真}, \text{偽})$ を渡されたとします。検証器は各節を順に評価します。

• 第 1 節 $(x_1 \lor \lnot x_2 \lor x_3)$：$x_1 =$ 真なので真。
• 第 2 節 $(\lnot x_1 \lor x_2)$：$\lnot x_1 =$ 偽ですが $x_2 =$ 真なので真。
• 第 3 節 $(\lnot x_2 \lor \lnot x_3)$：$\lnot x_2 =$ 偽ですが $\lnot x_3 =$ 真なので真。
• 第 4 節 $(x_1 \lor x_3)$：$x_1 =$ 真なので真。

4 節すべてが真なので $\alpha$ は $\varphi$ を充足し、$\langle \varphi \rangle \in \mathrm{SAT}$ が確かめられました。評価したリテラルは全部で 9 個、演算量は論理式の長さに比例します。証明書の長さは変数の個数 $n$ ビットで、明らかに論理式の長さ以下です。したがって $\mathrm{SAT} \in \mathrm{NP}$ です。

一方、割当を探す側は $2^n$ 通りの候補を持ちます。この例では $2^3 = 8$ 通りなので総当たりでも一瞬ですが、$n = 100$ なら §1 で見たとおり宇宙年齢の 2900 倍かかります。検算が $O(n)$、探索が $2^n$。この落差が P vs NP 問題の正体です。

注意 4.5

定義 4.1 は yes と no を対等に扱っていません。$\varphi$ が充足可能なら「この割当を見よ」で済みますが、$\varphi$ が充足不能であることを短く納得させる方法は知られていません。そこで

$$\mathrm{coNP} = \{\, L \subseteq \Sigma^{*} : \Sigma^{*} \setminus L \in \mathrm{NP} \,\}$$

と定義します。$\mathrm{NP} = \mathrm{coNP}$ かどうかも未解決で、$\mathrm{P} = \mathrm{NP}$ ならば $\mathrm{NP} = \mathrm{coNP}$ が従います（演習 9.1 と 演習 9.4）。

例 4.6（巡回セールスマン問題（決定版））

入力は $n$ 都市の完全グラフ、各辺 $\{i,j\}$ の非負整数重み $w(i,j)$、および閾値 $k$ です。問いは「全都市をちょうど 1 回ずつ訪れて出発点に戻る閉路で、重みの総和が $k$ 以下のものが存在するか」です。この言語を $\mathrm{TSP}$ と書きます。

4 都市 $A, B, C, D$ で $w(A,B) = 3$、$w(A,C) = 8$、$w(A,D) = 5$、$w(B,C) = 4$、$w(B,D) = 9$、$w(C,D) = 6$ とします。巡回路は回転と反転を同一視すると $(4-1)!/2 = 3$ 通りで、それぞれの長さは次のとおりです。

• $A \to B \to C \to D \to A$：$3 + 4 + 6 + 5 = 18$
• $A \to B \to D \to C \to A$：$3 + 9 + 6 + 8 = 26$
• $A \to C \to B \to D \to A$：$8 + 4 + 9 + 5 = 26$

したがって最短巡回路の長さは $18$ で、$k = 18$ なら答えは yes、$k = 17$ なら no です。$k = 18$ の場合の証明書は都市の並び $(A, B, C, D)$ で、これは各都市の番号を $\lceil \log_2 n \rceil$ ビットで書けば $O(n \log n)$ ビットに収まります。検証器は「並びが全都市の順列であること」を $O(n)$ で確かめ、$n$ 回の加算で総和を求め、$k$ と 1 回比較します。以上より $\mathrm{TSP} \in \mathrm{NP}$ です。

検証は 4 辺の重みの和（3 回の加算）と 1 回の比較で終わりましたが、最小値を出すには 3 通りを全部調べる必要がありました。$n = 30$ ならこの「3 通り」が $4.4 \times 10^{30}$ 通りになります。

命題 4.7

$\mathrm{P} \subseteq \mathrm{NP}$ が成り立ちます。

証明（命題 4.7）

$L \in \mathrm{P}$ とし、定義 3.1 により $L$ を多項式時間で判定する決定性機械 $M$ を取ります。検証器を $V(x, y) := M(x)$、すなわち第 2 引数を無視して $M$ を走らせる機械と定め、証明書長の上限多項式を定数多項式 $p(n) = 0$ とします。

$|y| \le 0$ を満たす $y$ は空列 $\varepsilon$ のみです。したがって

$$\exists y \ \bigl[\, |y| \le p(|x|) \ \text{かつ} \ V(x,y) = 1 \,\bigr] \iff V(x, \varepsilon) = 1 \iff M(x) = 1 \iff x \in L$$

となり、定義 4.1 の条件が満たされます。$V$ は $M$ と同じ多項式時間で停止します。よって $L \in \mathrm{NP}$ です。

∎

命題 4.8

$\mathrm{EXP} = \bigcup_{c \ge 1} \mathrm{TIME}(2^{n^{c}})$ とおきます。このとき $\mathrm{NP} \subseteq \mathrm{EXP}$ が成り立ちます。

証明（命題 4.8）

$L \in \mathrm{NP}$ とし、定義 4.1 の検証器 $V$ と多項式 $p$ を取ります。$V$ の実行時間を多項式 $r$ で抑えます。次の決定性アルゴリズムを考えます。入力 $x$（長さ $n$）に対し、長さ $0, 1, \ldots, p(n)$ のビット列 $y$ をすべて列挙し、各 $y$ について $V(x, y)$ を計算する。1 つでも $1$ を返せば受理、すべて $0$ なら拒否する。

正しさは 定義 4.1 の同値式そのものです。証明書が存在すればこの列挙が必ずそれを含み、存在しなければどの $y$ も $V(x,y) = 1$ を与えません。

実行時間を数えます。列挙する $y$ の個数は

$$\sum_{i=0}^{p(n)} 2^{i} = 2^{p(n)+1} - 1$$

個です。各 $y$ について $V(x,y)$ の計算に高々 $r(n + p(n))$ ステップかかるので、総時間は $\bigl(2^{p(n)+1} - 1\bigr) \cdot r\bigl(n + p(n)\bigr)$ 以下です。$r(n + p(n))$ は $n$ の多項式なので、この総時間はある定数 $c$ に対し $2^{n^{c}}$ で抑えられます。よって $L \in \mathrm{EXP}$ です。

∎

次の系のねらいは、P と NP の間か、NP とその上のクラス EXP（指数時間で解ける問題の全体）の間のどちらかには、必ず隙間があると言うことです。P と EXP が違うことは時間階層定理（計算時間を十分に増やすと解ける問題が本当に増える、という定理）から分かっているので、間にある NP は両側とくっつくことはできません。

系 4.9

$\mathrm{P} \ne \mathrm{NP}$ と $\mathrm{NP} \ne \mathrm{EXP}$ の少なくとも一方が成り立ちます。

証明（系 4.9）

時間階層定理により $\mathrm{P} \subsetneq \mathrm{EXP}$、特に $\mathrm{P} \ne \mathrm{EXP}$ です（この定理は対角線論法で証明されます。証明は Sipser『Introduction to the Theory of Computation』第 9 章、または Arora–Barak 第 3 章を参照してください）。

いま仮に $\mathrm{P} = \mathrm{NP}$ かつ $\mathrm{NP} = \mathrm{EXP}$ だったとすると、$\mathrm{P} = \mathrm{EXP}$ となって矛盾します。命題 4.7 と 命題 4.8 より $\mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{EXP}$ なので、2 つの包含のうち少なくとも一方は真の包含です。

∎

つまり「$\mathrm{NP}$ は $\mathrm{P}$ より真に大きい」か「$\mathrm{NP}$ は $\mathrm{EXP}$ より真に小さい」かのどちらかは確実に正しく、私たちはどちらか分からない、というのが現状です。分離が 1 つも証明できないわけではありません。証明できないのは、この特定の場所での分離です。

5. 帰着 — 難しさを移す道具

$\mathrm{NP}$ の中で「最も難しい問題」を定義するには、2 つの問題の難しさを比べる物差しが要ります。その物差しが帰着です。考え方は素朴で、「問題 $A$ の入力を、答えが変わらないように問題 $B$ の入力へ翻訳できるなら、$B$ を解く道具は $A$ を解く道具にもなる」というものです。

定義 5.1（多項式時間多対一帰着（カープ帰着））↗

言語 $A, B \subseteq \Sigma^{*}$ について、関数 $f : \Sigma^{*} \to \Sigma^{*}$ が次の 2 条件を満たすとき、$f$ を $A$ から $B$ への多項式時間多対一帰着といい、$A \le_{\mathrm{p}} B$ と書きます。

1. $f$ は決定性チューリング機械により、入力 $x$ の長さの多項式時間で計算できる。
2. すべての $x \in \Sigma^{*}$ に対して、$x \in A \iff f(x) \in B$ が成り立つ。

条件 2 は両方向であることに注意してください。$f$ は yes の入力を yes の入力へ、no の入力を no の入力へ移さなければなりません。また条件 1 により、$f$ 自身が $A$ を解いてしまうことはできません（$A$ が難しければ多項式時間では解けないからです）。$f$ にできるのは、あくまで問題の言い換えです。

向きの読み方も重要です。$A \le_{\mathrm{p}} B$ は「$A$ は $B$ より難しくない」を意味します。不等号の向きと「難しさ」の向きが一致するように記号が選ばれています。

帰着 A ≤p B を使って A を解く手順

次の定理は、帰着が「難しさを運ぶ」道具として使えることを保証します。証明は、変換 $f$ と $B$ の解法を続けて走らせたときの時間を数えるだけです。冒頭の「多項式は単調非減少としてよい」という準備は、時間の見積もりを書きやすくするための技術的な下ごしらえなので、初めは読み飛ばして構いません。

定理 5.2（帰着の基本性質）✓

$A, B, C \subseteq \Sigma^{*}$ とし、$A \le_{\mathrm{p}} B$ が成り立つとします。このとき次が成り立ちます。

1. $B \in \mathrm{P}$ ならば $A \in \mathrm{P}$。
2. $B \in \mathrm{NP}$ ならば $A \in \mathrm{NP}$。
3. さらに $B \le_{\mathrm{p}} C$ ならば $A \le_{\mathrm{p}} C$（推移律）。

証明（定理 5.2）

$A \le_{\mathrm{p}} B$ を与える帰着関数を $f$ とし、定義 5.1 の条件 1 により $f$ の計算時間を多項式 $q$ で抑えます。まず全体で使う不等式を 1 つ用意します。チューリング機械は 1 ステップで高々 1 文字しか書き込めないので、$q(n)$ ステップで出力できる文字列の長さも高々 $q(n)$ です。すなわち

$$|f(x)| \le q(|x|) \quad (\forall x \in \Sigma^{*}).$$

また、以下では時間や長さの上界に使う多項式 $r$ を単調非減少と仮定してよいことを使います。$r(m) = \sum_{i} a_i m^i$ の係数を絶対値に置き換えた $r'(m) = \sum_i \lvert a_i \rvert m^i$ を取れば、$r'$ は同じ次数の多項式で $m \ge 0$ において単調非減少、かつ $r(m) \le r'(m)$ を満たすので、上界としては $r$ を $r'$ で置き換えられるからです。

(1) の証明。 $B \in \mathrm{P}$ とし、定義 3.1 により $B$ を時間 $r$ で判定する機械 $M_B$ を取ります（$r$ は単調非減少としてよい）。次のアルゴリズム $M_A$ を作ります。入力 $x$ に対し $f(x)$ を計算し、$M_B(f(x))$ の出力をそのまま返す。

正しさ：定義 5.1 の条件 2 より $x \in A \iff f(x) \in B$ であり、$M_B$ は $f(x) \in B$ を正しく判定するので、$M_A$ は $x \in A$ を正しく判定します。

時間：$f(x)$ の計算に $q(n)$ ステップ、$M_B$ の実行に $r(|f(x)|) \le r(q(n))$ ステップ（$r$ の単調性と上の不等式を使いました）。合計は $q(n) + r(q(n))$ で、多項式の合成と和はまた多項式なので、$M_A$ は多項式時間です。よって $A \in \mathrm{P}$ です。

(2) の証明。 $B \in \mathrm{NP}$ とし、定義 4.1 により $B$ の検証器 $V_B$ と証明書長の多項式 $p_B$（単調非減少としてよい）を取ります。$A$ の検証器を

$$V_A(x, y) := V_B\bigl(f(x),\, y\bigr)$$

と定め、証明書長の多項式を $p_A(n) := p_B(q(n))$ とします。

正しさ：$x \in A$ とすると条件 2 より $f(x) \in B$ なので、$|y| \le p_B(|f(x)|)$ かつ $V_B(f(x), y) = 1$ となる $y$ が存在します。$|f(x)| \le q(n)$ と $p_B$ の単調性から $p_B(|f(x)|) \le p_B(q(n)) = p_A(n)$ なので、この $y$ は $|y| \le p_A(|x|)$ を満たし、$V_A(x,y) = 1$ です。逆に $|y| \le p_A(|x|)$ かつ $V_A(x,y) = 1$ となる $y$ があれば $V_B(f(x), y) = 1$ なので $f(x) \in B$、条件 2 より $x \in A$ です。

時間：$V_A$ は $f(x)$ の計算に $q(n)$ ステップ、続いて $V_B$ の実行に $(|f(x)| + |y|)$ の多項式時間を要し、$|f(x)| \le q(n)$、$|y| \le p_A(n)$ はいずれも $n$ の多項式で抑えられるので、全体で $n$ の多項式時間です。よって $A \in \mathrm{NP}$ です。

(3) の証明。 $B \le_{\mathrm{p}} C$ を与える帰着関数を $g$、その計算時間の上界を多項式 $s$（単調非減少）とします。合成 $h(x) := g(f(x))$ を考えます。

正しさ：$x \in A \iff f(x) \in B$（$f$ の性質）$\iff g(f(x)) \in C$（$g$ の性質）です。

時間：$f(x)$ の計算に $q(n)$、$g$ の計算に $s(|f(x)|) \le s(q(n))$ ステップで、合計 $q(n) + s(q(n))$ は多項式です。よって $h$ は多項式時間で計算でき、$A \le_{\mathrm{p}} C$ が成り立ちます。

∎

定理 5.2 の 1 は日常的には対偶の形で使われます。すなわち「$A$ が多項式時間で解けないなら、$B$ も多項式時間で解けない」。難しさは帰着の矢印を逆向きに伝わります。

6. NP 完全性 — 最も難しい問題たち

定義 6.1（NP 困難と NP 完全）↗

言語 $B \subseteq \Sigma^{*}$ が NP 困難であるとは、すべての $L \in \mathrm{NP}$ に対して $L \le_{\mathrm{p}} B$ が成り立つことをいいます。$B$ が NP 困難であり、かつ $B \in \mathrm{NP}$ でもあるとき、$B$ は NP 完全であるといいます。

NP 困難とは「$\mathrm{NP}$ のすべての問題より難しい」ということです。$\mathrm{NP}$ には無限個の言語があるので、この条件は一見して満たしようがないほど強く見えます。ところが実際には満たす問題が存在し、しかも大量にあります。

系 6.2

$B$ を NP 完全な言語とします。このとき次が成り立ちます。

1. $B \in \mathrm{P}$ ならば $\mathrm{P} = \mathrm{NP}$。
2. $\mathrm{P} \ne \mathrm{NP}$ ならば $B \notin \mathrm{P}$、すなわちいかなる NP 完全問題も多項式時間では解けない。

証明（系 6.2）

1 を示します。$B \in \mathrm{P}$ と仮定し、任意に $L \in \mathrm{NP}$ を取ります。$B$ は NP 困難なので 定義 6.1 より $L \le_{\mathrm{p}} B$ です。$B \in \mathrm{P}$ なので 定理 5.2 の 1 を適用して $L \in \mathrm{P}$ を得ます。$L$ は任意だったので $\mathrm{NP} \subseteq \mathrm{P}$ です。他方 命題 4.7 より $\mathrm{P} \subseteq \mathrm{NP}$ なので、$\mathrm{P} = \mathrm{NP}$ が従います。

2 は 1 の対偶です。$B \in \mathrm{P}$ だったとすると 1 により $\mathrm{P} = \mathrm{NP}$ となり、仮定 $\mathrm{P} \ne \mathrm{NP}$ に反します。

∎

これが NP 完全性の威力です。NP 完全問題は $\mathrm{NP}$ 全体の運命を背負っており、そのうちどれか 1 つでも多項式時間で解ければ、残り全部が一斉に多項式時間で解けます。逆にいえば、ある問題が NP 完全だと分かれば、その問題に対する多項式時間アルゴリズムを探すのは、P vs NP 問題を解くのと同じ難しさの仕事だと分かります。実務でこれは「探すのをやめて別の戦略に切り替えろ」という強い信号になります。

次の定理は、NP 完全な問題が実際に 1 つ存在することを示します。考え方は、NP の問題を解く機械の動きを「時刻ごとのテープの様子を並べた表」として書き、その表が正しい計算になっていることを論理式で表す、というものです。表の各マスは前の行の近くのマスだけで決まるので、「正しい計算である」という条件を小さな節の集まりで書けます。

定理 6.3（Cook–Levin の定理）✓

$\mathrm{SAT}$ は NP 完全です。すなわち $\mathrm{SAT} \in \mathrm{NP}$ であり、かつすべての $L \in \mathrm{NP}$ に対して $L \le_{\mathrm{p}} \mathrm{SAT}$ が成り立ちます。

証明（定理 6.3）

$\mathrm{SAT} \in \mathrm{NP}$ は 例 4.4 で確かめました。証明書として真理値割当を渡し、各節を順に評価すれば、論理式の長さに比例する時間で検証できます。

NP 困難性の骨子だけをここに述べ、詳細は本記事末尾の Appendix に回します。$L \in \mathrm{NP}$ を任意に取り、注意 4.2 の同値性により $L$ を時間 $T(n)$（$T$ は多項式）で受理する非決定性チューリング機械 $N$ を取ります。入力 $x$ に対する $N$ の計算の様子は、時刻を行、テープの位置を列とする $(T(n)+1)$ 行の計算表として書けます。この表の各マスに「どの記号が入っているか」を表す命題変数を用意し、「表の各マスの中身がちょうど 1 つに決まる」「第 0 行が入力 $x$ の初期状態を表す」「隣り合う 2 行が $N$ の遷移規則と整合する」「どこかに受理状態が現れる」という 4 種類の条件を CNF 論理式 $\varphi_x$ に書き下します。変数も節も $O(T(n)^2)$ 個で済み、$\varphi_x$ は $x$ から多項式時間で構成できます。構成から、$\varphi_x$ の充足割当と $N$ の $x$ に対する受理計算とが 1 対 1 に対応するので、$x \in L \iff \langle \varphi_x \rangle \in \mathrm{SAT}$ が成り立ちます。これが求める帰着です。

∎

注意 6.4

この定理は Stephen Cook が 1971 年に、Leonid Levin が 1973 年に独立に得たものです（Levin は当時ソ連にいて、Cook の結果を知りませんでした）。1972 年には Richard Karp が、SAT からの帰着によって 21 個の組合せ問題が NP 完全であることを示し、NP 完全性が理論の飾りではなく実務に遍在する現象であることを明らかにしました。

次の系の証明の中心は、長い節を 3 リテラルの節の鎖に分ける変換です。たとえば $k = 5$ の節 $(\ell_1 \lor \ell_2 \lor \ell_3 \lor \ell_4 \lor \ell_5)$ は、新変数 $z_1, z_2$ を使って $(\ell_1 \lor \ell_2 \lor z_1) \land (\lnot z_1 \lor \ell_3 \lor z_2) \land (\lnot z_2 \lor \ell_4 \lor \ell_5)$ に置き換わります。$\ell_3$ だけが真なら $z_1$ を真、$z_2$ を偽にすると、3 つの節は順に $z_1$、$\ell_3$、$\lnot z_2$ で真になります。$\ell_4$ だけが真なら $z_1, z_2$ をともに真にすると、順に $z_1$、$z_2$、$\ell_4$ で真になります。5 個のリテラルがすべて偽だと、第 1 節から $z_1$ が真、第 2 節から $z_2$ が真となり、第 3 節が偽になってしまいます。

系 6.5

$\mathrm{3SAT}$ は NP 完全です。

証明（系 6.5）

$\mathrm{3SAT} \in \mathrm{NP}$ は $\mathrm{SAT}$ と同じ理由（証明書は真理値割当）で成り立ちます。NP 困難性を示すには、定理 6.3 と 定理 5.2 の 3（推移律）により、$\mathrm{SAT} \le_{\mathrm{p}} \mathrm{3SAT}$ を示せば十分です。実際、任意の $L \in \mathrm{NP}$ に対し $L \le_{\mathrm{p}} \mathrm{SAT} \le_{\mathrm{p}} \mathrm{3SAT}$ から $L \le_{\mathrm{p}} \mathrm{3SAT}$ が従います。

CNF 論理式 $\varphi$ の各節 $C = (\ell_1 \lor \cdots \lor \ell_k)$ を、リテラル数がちょうど 3 の節の集まりに置き換えます。節ごとに新しい変数を使い、他の節とは共有しません。

• $k = 1$ のとき：新変数 $y_1, y_2$ を使い、$(\ell_1 \lor y_1 \lor y_2) \land (\ell_1 \lor \lnot y_1 \lor y_2) \land (\ell_1 \lor y_1 \lor \lnot y_2) \land (\ell_1 \lor \lnot y_1 \lor \lnot y_2)$ に置き換えます。$y_1, y_2$ の 4 通りの値すべてを潰しているので、この 4 節が同時に真になるのは $\ell_1$ が真のとき、かつそのときに限ります。
• $k = 2$ のとき：新変数 $y$ を使い、$(\ell_1 \lor \ell_2 \lor y) \land (\ell_1 \lor \ell_2 \lor \lnot y)$ とします。同様に、$\ell_1 \lor \ell_2$ が真であることと同値です。
• $k = 3$ のとき：そのまま残します。
• $k \ge 4$ のとき：新変数 $z_1, \ldots, z_{k-3}$ を使い、次の $k-2$ 個の節に置き換えます。

$$(\ell_1 \lor \ell_2 \lor z_1) \ \land \ \bigwedge_{i=2}^{k-3} (\lnot z_{i-1} \lor \ell_{i+1} \lor z_i) \ \land \ (\lnot z_{k-3} \lor \ell_{k-1} \lor \ell_k)$$

$k \ge 4$ の場合の同値性を確かめます。まず、ある $\ell_t$ が真だとします。$z_i$ を $i \le t-2$ のとき真、$i > t-2$ のとき偽と定めます。第 1 節は、$t \le 2$ なら $\ell_t$ が真で、$t \ge 3$ なら $z_1$ が真なので充足されます。中間の第 $i$ 節 $(\lnot z_{i-1} \lor \ell_{i+1} \lor z_i)$ は、$i \le t-2$ なら $z_i$ が真、$i = t-1$ なら $\ell_{i+1} = \ell_t$ が真、$i \ge t$ なら $z_{i-1}$ が偽なので $\lnot z_{i-1}$ が真で、いずれの場合も充足されます。最後の節は、$t \ge k-1$ なら $\ell_t$ が真、$t \le k-2$ なら $z_{k-3}$ が偽なので $\lnot z_{k-3}$ が真となり充足されます。

逆に $\ell_1, \ldots, \ell_k$ がすべて偽だとします。第 1 節から $z_1$ は真でなければなりません。$z_{i-1}$ が真だと分かっているとき、第 $i$ 節では $\lnot z_{i-1}$ が偽、$\ell_{i+1}$ も偽なので $z_i$ が真でなければなりません。これを $i = 2, \ldots, k-3$ と繰り返すと $z_{k-3}$ が真です。すると最後の節 $(\lnot z_{k-3} \lor \ell_{k-1} \lor \ell_k)$ は 3 つのリテラルすべてが偽になり、充足できません。したがって、置き換え後の論理式が充足可能であることと、もとの節が充足可能であることは同値です。

新変数は節ごとに独立なので、$\varphi$ 全体としても「$\varphi$ が充足可能 $\iff$ 置き換え後の 3-CNF が充足可能」が成り立ちます。生成される節の総数は、節 $C$ あたり高々 $\max(k-2, 4)$ 個なので $\varphi$ の長さの定数倍で抑えられ、変換は入力の長さに対して線形時間（特に多項式時間）で実行できます。以上より $\mathrm{SAT} \le_{\mathrm{p}} \mathrm{3SAT}$ です。

∎

論理式の問題からグラフの問題へも、同じやり方で難しさを運べます。次の帰着は最も美しいものの 1 つで、証明を完全に追えます。

定理 6.6（独立集合問題の NP 完全性）✓

無向グラフ $G = (V, E)$ の頂点部分集合 $S \subseteq V$ が独立集合であるとは、$S$ のどの相異なる 2 頂点も $E$ で結ばれていないことをいいます。言語

$$\mathrm{INDSET} = \{\, \langle G, k \rangle : G \ \text{は大きさ} \ k \ \text{の独立集合を持つ無向グラフ} \,\}$$

について、$\mathrm{3SAT} \le_{\mathrm{p}} \mathrm{INDSET}$ が成り立ちます。特に $\mathrm{INDSET}$ は NP 完全です。

証明（定理 6.6）

まず $\mathrm{INDSET} \in \mathrm{NP}$ です。証明書として頂点集合 $S$ を渡せば、$|S| = k$ の確認と、$S$ の全頂点対が非隣接であることの確認が $O(k^2)$ 回の辺の有無の判定で済み、入力サイズの多項式時間です。

帰着を構成します。3-CNF 論理式 $\varphi = C_1 \land \cdots \land C_m$、$C_i = (\ell_{i,1} \lor \ell_{i,2} \lor \ell_{i,3})$ が与えられたとき、グラフ $G_\varphi$ を次のように作ります。

• 頂点：各 $i \in \{1,\ldots,m\}$、$j \in \{1,2,3\}$ に対して頂点 $v_{i,j}$ を 1 つ置きます。頂点 $v_{i,j}$ は「第 $i$ 節の $j$ 番目のリテラルの出現」に対応します。頂点数は $3m$ です。
• 節内の辺：同じ $i$ について $j \ne j'$ なら $v_{i,j}$ と $v_{i,j'}$ を結びます。各節が三角形になります。
• 矛盾辺：$i \ne i'$ で、$\ell_{i,j}$ と $\ell_{i',j'}$ が互いに否定（一方が $x$、他方が $\lnot x$）であるとき、$v_{i,j}$ と $v_{i',j'}$ を結びます。

そして $f(\langle \varphi \rangle) := \langle G_\varphi, m \rangle$ と定めます。$G_\varphi$ の頂点は $3m$ 個、辺は高々 $\binom{3m}{2} = O(m^2)$ 本で、どの 2 頂点を結ぶかは対応するリテラルを見るだけで判定できるので、$f$ は $O(m^2)$ 時間、特に多項式時間で計算できます。

($\Rightarrow$) $\varphi$ が充足可能ならば $G_\varphi$ は大きさ $m$ の独立集合を持つ。 充足割当 $\alpha$ を取ります。各節 $C_i$ は $\alpha$ の下で真なので、真になるリテラルが少なくとも 1 つあります。その 1 つを選んで添字を $j(i)$ とし、$S = \{\, v_{i,j(i)} : i = 1,\ldots,m \,\}$ とおきます。節ごとに 1 頂点ずつ選んだので $|S| = m$ です。$S$ が独立集合であることを見ます。節内の辺は同じ $i$ の頂点どうしを結びますが、$S$ には各 $i$ につき 1 頂点しかないので、節内の辺の両端が $S$ に入ることはありません。矛盾辺については、$v_{i,j(i)}$ と $v_{i',j(i')}$ が矛盾辺で結ばれているとすると $\ell_{i,j(i)}$ と $\ell_{i',j(i')}$ は互いに否定ですが、$\alpha$ の下で両方とも真であることになり、$\alpha$ が写像であることに矛盾します。よって $S$ は独立集合です。

($\Leftarrow$) $G_\varphi$ が大きさ $m$ の独立集合を持つならば $\varphi$ は充足可能。 独立集合 $S$、$|S| = m$ を取ります。節内の辺により、各 $i$ について $S \cap \{v_{i,1}, v_{i,2}, v_{i,3}\}$ は高々 1 個です（2 個入れば節内の辺で結ばれてしまいます）。この上限が $m$ 個の $i$ について成り立ち、かつ $|S| = m$ なので、各 $i$ についてちょうど 1 個です。その頂点を $v_{i,j(i)}$ と書きます。

割当 $\alpha$ を次のように定めます。各 $i$ について、$\ell_{i,j(i)}$ が真になるように、対応する変数の値を決めます（$\ell_{i,j(i)} = x$ なら $x$ を真、$\ell_{i,j(i)} = \lnot x$ なら $x$ を偽）。この指定に矛盾が起きないことを確かめます。もし 2 つの添字 $i \ne i'$ が同じ変数 $x$ に相反する値を要求したとすると、$\ell_{i,j(i)}$ と $\ell_{i',j(i')}$ は互いに否定であり、構成により $v_{i,j(i)}$ と $v_{i',j(i')}$ は矛盾辺で結ばれています。これは $S$ が独立集合であることに反します。どの $i$ からも指定されなかった変数には偽を割り当てます。

こうして得た $\alpha$ の下で、各節 $C_i$ はリテラル $\ell_{i,j(i)}$ が真なので真です。よって $\alpha$ は $\varphi$ を充足します。

以上で $\langle \varphi \rangle \in \mathrm{3SAT} \iff f(\langle \varphi \rangle) \in \mathrm{INDSET}$ が示され、$\mathrm{3SAT} \le_{\mathrm{p}} \mathrm{INDSET}$ が成り立ちます。NP 完全性は、系 6.5 で $\mathrm{3SAT}$ が NP 困難であることと、定理 5.2 の 3 による推移律から従います。

∎

例 6.7（帰着を具体的に走らせる）

$$\varphi = (x_1 \lor \lnot x_2 \lor \lnot x_3) \land (\lnot x_1 \lor x_2 \lor x_3) \land (x_1 \lor x_2 \lor x_3)$$

に 定理 6.6 の構成を適用します。$m = 3$ なので頂点は 9 個で、対応は次のとおりです。

頂点	$v_{1,1}$	$v_{1,2}$	$v_{1,3}$	$v_{2,1}$	$v_{2,2}$	$v_{2,3}$	$v_{3,1}$	$v_{3,2}$	$v_{3,3}$
リテラル	$x_1$	$\lnot x_2$	$\lnot x_3$	$\lnot x_1$	$x_2$	$x_3$	$x_1$	$x_2$	$x_3$

辺を数えます。節内の辺は三角形 3 個で $3 \times 3 = 9$ 本です。矛盾辺は、$x_1$ を含む $v_{1,1}, v_{3,1}$ と $\lnot x_1$ の $v_{2,1}$ の間で 2 本、$\lnot x_2$ の $v_{1,2}$ と $x_2$ を含む $v_{2,2}, v_{3,2}$ の間で 2 本、$\lnot x_3$ の $v_{1,3}$ と $x_3$ を含む $v_{2,3}, v_{3,3}$ の間で 2 本、合計 6 本です。全部で 15 本の辺を持つ 9 頂点のグラフができました。

$S = \{v_{1,1},\, v_{2,2},\, v_{3,1}\}$ が独立集合かどうかを確かめます。3 頂点はそれぞれ別の節に属するので節内の辺はありません。矛盾辺については、$v_{1,1}$ と $v_{3,1}$ はどちらも $x_1$（互いに否定ではない）、$v_{1,1}$ と $v_{2,2}$ は $x_1$ と $x_2$、$v_{2,2}$ と $v_{3,1}$ は $x_2$ と $x_1$ で、いずれも矛盾していません。よって $S$ は大きさ 3 の独立集合です。

証明の ($\Leftarrow$) 方向の手続きに従って割当を復元します。$v_{1,1} = x_1$ から $x_1$ は真、$v_{2,2} = x_2$ から $x_2$ は真、$v_{3,1} = x_1$ からも $x_1$ は真（矛盾なし）。$x_3$ はどこからも指定されないので偽とします。$\alpha = (x_1, x_2, x_3) = (\text{真}, \text{真}, \text{偽})$ を $\varphi$ に代入すると、第 1 節は $(\text{真} \lor \text{偽} \lor \text{真}) =$ 真、第 2 節は $(\text{偽} \lor \text{真} \lor \text{偽}) =$ 真、第 3 節は $(\text{真} \lor \text{真} \lor \text{偽}) =$ 真で、確かに $\varphi$ を充足しています。

なお、このグラフに大きさ 4 の独立集合は存在しません。3 つの三角形から高々 1 頂点ずつしか取れないので、独立集合の大きさは 3 が上限だからです。

上の例の 3SAT 論理式から、独立集合への帰着で作られるグラフ。実線の三角形が節内の辺、曲がった線が矛盾辺で、塗りつぶした 3 頂点が大きさ 3 の独立集合。

注意 6.8

Karp が 1972 年に挙げた 21 問題を含め、現在では数千の問題が NP 完全であると知られています。代表的なものを挙げます。証明（帰着の構成）は Garey–Johnson『Computers and Intractability』の付録、または Sipser 第 7 章にまとまっています。

問題	入力	問い	証明書
SAT	CNF 論理式 $\varphi$	充足割当が存在するか	真理値割当
3SAT	各節が 3 リテラルの CNF	同上	真理値割当
独立集合	グラフ $G$、整数 $k$	大きさ $k$ の独立集合があるか	頂点の集合
頂点被覆	グラフ $G$、整数 $k$	大きさ $k$ の頂点被覆があるか	頂点の集合
クリーク	グラフ $G$、整数 $k$	大きさ $k$ の完全部分グラフがあるか	頂点の集合
ハミルトン閉路	グラフ $G$	全頂点をちょうど 1 度通る閉路があるか	頂点の並び
巡回セールスマン（決定版）	重み付き完全グラフ、整数 $k$	総重み $k$ 以下の巡回路があるか	都市の並び
部分和	正整数の列、目標値 $t$	和が $t$ の部分列があるか	添字の集合
3 彩色	グラフ $G$	隣接頂点が同色にならない 3 彩色があるか	頂点への色の割当

一方、$\mathrm{P}$ に属する近縁の問題と並べると境界の細さが分かります。2SAT（各節が 2 リテラル）は $\mathrm{P}$、3SAT は NP 完全。2 彩色（二部グラフ判定）は $\mathrm{P}$、3 彩色は NP 完全。オイラー閉路（各辺をちょうど 1 度通る閉路）は $\mathrm{P}$、ハミルトン閉路は NP 完全。最短経路は $\mathrm{P}$、最長単純路は NP 完全です（最長単純路では最適部分構造が壊れることについて 例 5.2［動的計画法］ を参照）。

P ≠ NP が正しい世界（左）と P = NP の世界（右）

左の図の「NP 中間」の帯が空でないことは、$\mathrm{P} \ne \mathrm{NP}$ を仮定すれば Ladner の定理（1975）から従います。すなわち $\mathrm{P} \ne \mathrm{NP}$ ならば、$\mathrm{NP}$ に属し、$\mathrm{P}$ にも属さず NP 完全でもない言語が存在します。整数分解の決定版とグラフ同型判定は、この帯にいるのではないかと予想されている代表例です。どちらも NP 完全であることは示されておらず、$\mathrm{P}$ に属することも示されていません。

7. P = NP なら何が起きるか

$\mathrm{P} = \mathrm{NP}$ の帰結を語る前に、1 つ技術的なギャップを埋めておきます。ここまで扱ってきたのは「解が存在するか」という決定問題だけですが、実務で欲しいのは解そのものです。$\mathrm{SAT}$ については、決定できれば解も構成できます。

命題 7.1（SAT の自己帰着性）✓

$\mathrm{SAT}$ を多項式時間で判定するアルゴリズム $D$ が存在すると仮定します。このとき、CNF 論理式 $\varphi$ を入力として、$\varphi$ が充足可能ならばその充足割当を 1 つ出力し、充足不能ならばその旨を出力する多項式時間アルゴリズムが存在します。

証明（命題 7.1）

$\varphi$ の変数を $x_1, \ldots, x_n$ とします。次のアルゴリズムを考えます。

1. $D(\varphi)$ を呼ぶ。答えが no なら「充足不能」を出力して終了する。
2. $\psi \leftarrow \varphi$ とおく。$i = 1, 2, \ldots, n$ について次を繰り返す。
   • $\psi$ の中の $x_i$ をすべて「真」に置き換えて簡約した論理式を $\psi^{+}$ とする（真になったリテラルを含む節は削除し、偽になったリテラルは節から取り除く）。
   • $D(\psi^{+})$ が yes なら $a_i \leftarrow$ 真、$\psi \leftarrow \psi^{+}$ とする。そうでなければ $a_i \leftarrow$ 偽とし、$\psi$ の中の $x_i$ をすべて「偽」に置き換えて簡約したものを新たな $\psi$ とする。
3. $(a_1, \ldots, a_n)$ を出力する。

正しさを示します。不変条件「ループの各回の開始時点で $\psi$ は充足可能」を $i$ に関する帰納法で確かめます。$i = 1$ の開始時は手順 1 により $\psi = \varphi$ が充足可能です。$i$ の回の開始時に $\psi$ が充足可能だとします。$\psi$ の充足割当 $\beta$ を 1 つ取ると、$\beta(x_i)$ は真か偽のいずれかで、その値に $x_i$ を固定した論理式も $\beta$ で充足されます。したがって $\psi^{+}$ と「$x_i$ を偽にした $\psi$」の少なくとも一方は充足可能です。アルゴリズムは $D$ を使ってまず $\psi^{+}$ を試し、それが充足可能でなければ偽の側を選びます。$\psi^{+}$ が充足不能なら偽の側が充足可能でなければならないので、いずれの分岐でも新しい $\psi$ は充足可能です。

ループ終了時、$\psi$ にはもう変数が残っていないので、簡約後の $\psi$ は定数「真」です（充足可能で変数を持たないのですから）。よって $(a_1,\ldots,a_n)$ は $\varphi$ を充足します。

計算時間は、$D$ の呼び出しが $n + 1$ 回、各回の置き換えと簡約が $O(|\varphi|)$ で、$D$ が多項式時間なので全体も多項式時間です。

∎

注意 7.2

一般の $L \in \mathrm{NP}$ についても、$\mathrm{P} = \mathrm{NP}$ ならば証明書を多項式時間で構成できます。定理 6.3 の帰着は計算表を通じて構成されるため、$\varphi_x$ の充足割当から $N$ の受理計算、したがって証明書が読み出せるからです。命題 7.1 で $\varphi_x$ の充足割当を作り、それを翻訳し直せば証明書が得られます。つまり $\mathrm{P} = \mathrm{NP}$ の下では「存在の判定」と「解の構成」は同じ計算量です。

7.1. 暗号は成立しなくなる

現代の暗号は「計算が難しい」ことに安全性を預けています。RSA は合成数の素因数分解、ディフィー–ヘルマンや楕円曲線暗号は離散対数、格子暗号は最短ベクトル問題の難しさを仮定しています。

$\mathrm{P} = \mathrm{NP}$ ならこれらは一斉に崩れます。理由は一般的です。多項式時間で計算できる関数 $f$ と多項式 $p$（逆像の長さの上限。暗号で使う関数は入力長と出力長が多項式で結ばれているので、この $p$ は取れます）について、言語

$$A_f = \{\, \langle y, u \rangle : \exists z \ \bigl[\, |z| \le p(|y|) \ \text{かつ} \ f(z) = y \ \text{かつ} \ z \ \text{の先頭部分が} \ u \,\bigr] \,\}$$

は $\mathrm{NP}$ に属します（証明書は $z$ そのもので、検証は $f(z)$ を計算して $y$ と比べ、先頭を照合するだけです）。$\mathrm{P} = \mathrm{NP}$ ならば $A_f \in \mathrm{P}$ なので、$u$ を 1 ビットずつ伸ばしながら $A_f$ を問い合わせることで、$f$ の逆像 $z$ を多項式時間で 1 ビットずつ確定できます。つまり一方向関数は存在しません。一方向関数がなければ、擬似乱数生成器も、それに立脚する現代的な共通鍵暗号の安全性証明も成り立ちません。共通鍵暗号を直接攻撃することもできます。平文と暗号文の対 $(m_1, c_1), \ldots, (m_t, c_t)$ が与えられたとき、「すべての $i$ で $E_k(m_i) = c_i$ となる鍵 $k$ が存在するか」は $\mathrm{NP}$ に属する（証明書は $k$）ので、$\mathrm{P} = \mathrm{NP}$ なら鍵を多項式時間で復元できます。

注意

逆は成り立ちません。$\mathrm{P} \ne \mathrm{NP}$ は安全な暗号の必要条件であって十分条件ではありません。$\mathrm{P} \ne \mathrm{NP}$ が保証するのは「最悪の入力では難しい」ことだけで、暗号に必要なのは「ランダムに生成した鍵に対してほとんど常に難しい」という平均計算量の困難性です。この 2 つを結ぶ含意は知られていません。仮に $\mathrm{P} \ne \mathrm{NP}$ が証明されても、それだけでは暗号の安全性は保証されません。

7.2. 最適化がすべて解けるようになる

例 4.6 の $\mathrm{TSP}$ で考えます。$\mathrm{P} = \mathrm{NP}$ なら $\mathrm{TSP} \in \mathrm{P}$ なので、閾値 $k$ を変えながら二分探索できます。辺重みが非負整数で最大値を $W$ とすると最適値は $0$ 以上 $nW$ 以下なので、$\lceil \log_2 (nW + 1) \rceil$ 回の問い合わせで最適値が確定します。$W$ は入力に 2 進法で書かれているので $\log_2 W$ は入力サイズ以下であり、問い合わせ回数は入力サイズの多項式（実際は線形）です。最適な巡回路そのものも、辺を 1 本ずつ「使う／使わない」と固定しながら同じ問い合わせを繰り返せば構成できます（命題 7.1 と同じ論法です）。

同じことが、物流の配送計画、工場のスケジューリング、集積回路の配置配線、時間割編成、無線周波数の割当、格子モデル上のタンパク質の折り畳みなど、NP 困難と分かっている膨大な数の最適化問題について一斉に起こります。これらは現在、近似アルゴリズムやヒューリスティクスで「そこそこの解」を出して運用されている領域です。$\mathrm{P} = \mathrm{NP}$ ならすべて厳密最適解が得られます。

7.3. 数学の証明が探索できるようになる

固定した形式体系（たとえば ZFC 集合論）で、命題 $\varphi$ の証明とは有限個の記号列であり、それが正しい証明かどうかは機械的に、証明の長さの多項式時間で検査できます。したがって言語

$$\{\, \langle \varphi, 1^{n} \rangle : \varphi \ \text{は長さ} \ n \ \text{以下の証明を持つ} \,\}$$

は $\mathrm{NP}$ に属します（証明書は証明そのもの。証明の長さの上限 $n$ を単進法 $1^n$ で書いてあるのは、入力サイズを $n$ 以上にして証明書長の多項式上限を成立させるための技術的な工夫です）。$\mathrm{P} = \mathrm{NP}$ ならこれは多項式時間で判定でき、命題 7.1 と同様の論法で証明そのものも構成できます。つまり「長さ $10^6$ 以内の証明を持つ未解決問題」は、すべて機械的に解決されます。これはまさにゲーデルが 1956 年の手紙で予見した帰結です。

ノート

ただし、$\mathrm{P} = \mathrm{NP}$ が証明されたとしても実用上の衝撃が直ちに来るとは限りません。指数 $100$ の多項式時間アルゴリズムでは何も実行できませんし、$\mathrm{P} = \mathrm{NP}$ を非構成的に示す証明（アルゴリズムを与えずに存在だけを示す証明）も原理的にはあり得ます。それでも、上に並べた帰結の異様な強さは、多くの研究者が $\mathrm{P} \ne \mathrm{NP}$ の側に賭ける理由になっています。

8. なぜ 50 年以上決着しないのか

$\mathrm{P} \ne \mathrm{NP}$ を示すには、$\mathrm{SAT}$ のような 1 つの問題について「いかなるアルゴリズムも多項式時間では解けない」を証明しなければなりません。上界（速いアルゴリズムがあること）は 1 つ作れば済みますが、下界はあらゆるアルゴリズムを同時に否定する必要があります。ここが難所です。

下界がまったく証明できないわけではありません。たとえば比較ソートに $\Omega(n \log n)$ 回の比較が必要なことは、決定木の葉が $n!$ 個以上必要という数え上げで示せます（定理 6.1［ソートアルゴリズム］。詳しくは ソートアルゴリズム を参照してください）。ただしこの証明は「比較しか使わない」というモデルの制限に強く依存しています。$\mathrm{P}$ vs $\mathrm{NP}$ ではアルゴリズムに一切の制限を置けないので、同じ手は使えません。

さらに、既存の証明技法が原理的に届かないことを示す「障壁」が 3 つ知られています。

相対化の壁（Baker–Gill–Solovay, 1975）。 ここでオラクルとは、ある問題の答えを 1 ステップで教えてくれる仮想的な「神託の箱」のことです。オラクル $A$ を与えて $\mathrm{P}^{A} = \mathrm{NP}^{A}$ となるものと、オラクル $B$ を与えて $\mathrm{P}^{B} \ne \mathrm{NP}^{B}$ となるものがともに存在します。対角線論法や機械のシミュレーションといった技法は、オラクルを付けてもそのまま通用する（相対化する）性質を持ちます。したがってそれらの技法だけでは、$\mathrm{P}$ と $\mathrm{NP}$ の関係をどちらにも決められません。停止問題の決定不能性の証明をそのまま流用しても届かない、ということです。

自然証明の壁（Razborov–Rudich, 1997）。 回路計算量の下界証明の多くは、「難しい関数」を特徴づける性質を作り、それが構成可能かつ多くの関数に当てはまる、という形をしています。この形（自然な証明）で $\mathrm{NP}$ の回路下界を示せてしまうと、十分に強い擬似乱数関数が存在しないことになり、暗号の標準的な仮定と矛盾します。つまり、既存の回路下界技法の自然な拡張では届きません。

代数化の壁（Aaronson–Wigderson, 2009）。 相対化の壁を破った技法として、論理式を多項式に持ち上げる算術化があります（$\mathrm{IP} = \mathrm{PSPACE}$ の証明などで使われました）。しかし算術化を含むように相対化の概念を一般化した「代数化」の下でも、同じ型の障壁が成り立ちます。

現在の見通しについて、Gasarch が 3 度（2002 年、2012 年、2019 年）行った研究者アンケートでは、回を追うごとに $\mathrm{P} \ne \mathrm{NP}$ 支持が増え、2019 年には回答者の約 9 割が $\mathrm{P} \ne \mathrm{NP}$ と予想しています。この問題は 2000 年にクレイ数学研究所のミレニアム懸賞問題に選ばれ、解決には 100 万ドルの賞金が懸けられています。

ヒント

実務家にとって重要なのは、目の前の問題が NP 完全だと分かったときに何をするかです。系 6.2 により多項式時間アルゴリズムを探すのは P vs NP を解くのと同じ仕事なので、方針を切り替えます。(1) 近似アルゴリズム（頂点被覆なら 2 近似が貪欲法で得られます）、(2) 入力の構造を利用するパラメータ化アルゴリズム、(3) 分枝限定法や SAT ソルバ・整数計画ソルバ。現代の SAT ソルバは数百万変数の産業インスタンスを日常的に解いています。最悪計算量が指数であることと、目の前のインスタンスが解けることは矛盾しません。NP 完全性は「このインスタンスは解けない」ではなく「すべてのインスタンスを保証付きで速く解くアルゴリズムは望み薄」と言っているだけです。

9. 演習

演習 9.1易

言語 $L$ の補集合を $\overline{L} = \Sigma^{*} \setminus L$ と書きます。

1. $L \in \mathrm{P}$ ならば $\overline{L} \in \mathrm{P}$ であることを示してください。
2. 同じ議論を 定義 4.1 に適用しようとすると、どこで破綻するかを説明してください。
3. $\mathrm{P} \subseteq \mathrm{NP} \cap \mathrm{coNP}$ を示してください。

解答

1. $L \in \mathrm{P}$ とし、定義 3.1 の機械 $M$ と多項式 $p$ を取ります。$M$ の受理状態と拒否状態を入れ替えた機械を $M'$ とします。$M$ はすべての入力で $p(|x|)$ ステップ以内に停止する（$M$ が無限ループしない）ので、$M'$ もすべての入力で $p(|x|)$ ステップ以内に停止し、$M'$ が $x$ を受理する $\iff$ $M$ が $x$ を拒否する $\iff$ $x \notin L$ $\iff$ $x \in \overline{L}$ です。よって $\overline{L} \in \mathrm{P}$ です。停止性の仮定が本質的である点に注意してください。

2. 定義 4.1 は yes 側と no 側で非対称です。$V$ の出力を反転した $V'$ を作っても、$\exists y\, [V'(x,y) = 1]$ は「$V(x,y) = 0$ となる $y$ が 1 つでもある」を意味するだけで、「すべての $y$ について $V(x,y) = 0$」（これが $x \notin L$ の内容）とは全く別の条件です。存在量化子を否定すると全称量化子になるので、証明書という道具がそのままでは使えません。実際、$\mathrm{NP} = \mathrm{coNP}$ かどうかは未解決です。

3. $L \in \mathrm{P}$ とします。命題 4.7 より $L \in \mathrm{NP}$ です。また 1 より $\overline{L} \in \mathrm{P}$ で、再び 命題 4.7 より $\overline{L} \in \mathrm{NP}$ なので、注意 4.5 の定義により $L \in \mathrm{coNP}$ です。よって $L \in \mathrm{NP} \cap \mathrm{coNP}$ です。

演習 9.2標準

部分和問題を $\mathrm{SUBSET\text{-}SUM} = \{\, \langle a_1, \ldots, a_n, t \rangle : \exists S \subseteq \{1,\ldots,n\},\ \sum_{i \in S} a_i = t \,\}$ とします。ここで $a_i$ と $t$ はいずれも 2 進法で書かれた正整数です。

1. $\mathrm{SUBSET\text{-}SUM} \in \mathrm{NP}$ を、証明書と検証器を明示して示してください。
2. 動的計画法 で学んだナップサック問題と同型の $O(nt)$ 時間の動的計画法（系 6.4［動的計画法］）は、なぜこの問題が $\mathrm{P}$ に属することの証明にならないのでしょうか。

解答

1. 証明書として、部分集合 $S$ を表す長さ $n$ のビット列 $y$（第 $i$ ビットが 1 なら $i \in S$）を取ります。$|y| = n$ であり、入力には $n$ 個の整数が書かれているので $n \le |x|$、したがって $p(m) = m$ とすれば証明書長の上限を満たします。検証器 $V(x,y)$ は、$y$ の 1 のビットに対応する $a_i$ を順に足し、その和を $t$ と比較して一致すれば 1 を返します。各 $a_i$ のビット長を高々 $L$ とすると、和は高々 $L + \lceil \log_2 n \rceil$ ビットに収まるので、加算 $n$ 回の総コストは $O(n(L + \log n))$ ビット演算です。入力サイズは $n$ 以上であり、かつ $L$ 以上でもあるので、この総コストは入力サイズの多項式で抑えられます。定義 4.1 の条件が満たされるので $\mathrm{SUBSET\text{-}SUM} \in \mathrm{NP}$ です。

2. 計算量 $O(nt)$ の $t$ は値であって入力サイズではないからです。注意 2.2 のとおり $t$ は 2 進法で書かれるので、その入力サイズは $\lceil \log_2 (t+1) \rceil$ ビットにすぎません。入力サイズを $m$ とすると $t$ は $2^{m}$ 程度まで大きくでき、$O(nt)$ は $O(n 2^{m})$、つまり入力サイズの指数時間になり得ます。このような計算量を擬多項式時間と呼びます。もし $t$ を単進法で書けば入力サイズが $t$ 以上になるので同じアルゴリズムが多項式時間になりますが、それは 注意 2.2 で禁じた水増しです。事実、$\mathrm{SUBSET\text{-}SUM}$ は NP 完全であることが知られているので、系 6.2 により、$\mathrm{P} \ne \mathrm{NP}$ ならば真の多項式時間アルゴリズムは存在しません。

演習 9.3標準

無向グラフ $G = (V, E)$ について、$C \subseteq V$ が頂点被覆であるとは、$E$ のどの辺も少なくとも一方の端点を $C$ に持つことをいいます。また $K \subseteq V$ がクリークであるとは、$K$ のどの相異なる 2 頂点も $E$ で結ばれていることをいいます。次の 2 つの言語を考えます。

$$\begin{aligned} \mathrm{VC} &= \{\, \langle G, k \rangle : G \ \text{は大きさ} \ k \ \text{の頂点被覆を持つ無向グラフ} \,\} \\ \mathrm{CLIQUE} &= \{\, \langle G, k \rangle : G \ \text{は大きさ} \ k \ \text{のクリークを持つ無向グラフ} \,\} \end{aligned}$$

1. $\mathrm{INDSET} \le_{\mathrm{p}} \mathrm{VC}$ を示してください。
2. $\mathrm{INDSET} \le_{\mathrm{p}} \mathrm{CLIQUE}$ を示してください。
3. これらから $\mathrm{VC}$ と $\mathrm{CLIQUE}$ が NP 完全であることを結論してください（$\mathrm{NP}$ への所属は認めてよいものとします）。

解答

1. 鍵になる観察は「$S$ が独立集合 $\iff$ $V \setminus S$ が頂点被覆」です。実際、$S$ が独立集合であることは「両端点がともに $S$ に入る辺が存在しない」ことで、これは「どの辺も少なくとも一方の端点が $V \setminus S$ に入る」ことと同値であり、後者は $V \setminus S$ が頂点被覆であることにほかなりません。

帰着関数を、$k \le |V|$ のとき $f(\langle G, k\rangle) = \langle G, |V| - k \rangle$、$k > |V|$ のときは固定した no インスタンス（たとえば辺のない 1 頂点グラフと $k = 2$）と定めます。$k \le |V|$ の場合、$G$ が大きさ $k$ の独立集合 $S$ を持つ $\iff$ $G$ が大きさ $|V| - k$ の頂点被覆 $V \setminus S$ を持つ、が上の観察から従います。$k > |V|$ の場合は大きさ $k$ の頂点部分集合自体が存在しないので、どちらも no です。$f$ は頂点数を数えて引き算するだけなので多項式時間です。

2. 補グラフ $\overline{G} = (V, \overline{E})$ を、$\overline{E} = \{\{u,v\} : u \ne v,\ \{u,v\} \notin E\}$ で定めます。$S$ が $G$ の独立集合である $\iff$ $S$ の相異なる 2 頂点はすべて $E$ で結ばれていない $\iff$ $S$ の相異なる 2 頂点はすべて $\overline{E}$ で結ばれている $\iff$ $S$ が $\overline{G}$ のクリークである、が定義から直ちに従います。よって $f(\langle G, k\rangle) = \langle \overline{G}, k \rangle$ が帰着です。補グラフの構成は隣接行列の $0$ と $1$ を（対角成分を除いて）反転するだけなので $O(|V|^{2})$ 時間、特に多項式時間です。

3. 定理 6.6 より $\mathrm{INDSET}$ は NP 困難、すなわち任意の $L \in \mathrm{NP}$ について $L \le_{\mathrm{p}} \mathrm{INDSET}$ です。これと 1、2 および 定理 5.2 の 3（推移律）を合わせると、$L \le_{\mathrm{p}} \mathrm{VC}$ および $L \le_{\mathrm{p}} \mathrm{CLIQUE}$ が任意の $L \in \mathrm{NP}$ について成り立ちます。よって両者は NP 困難で、$\mathrm{NP}$ に属するので 定義 6.1 により NP 完全です。

演習 9.4難

ある NP 完全な言語 $B$ が $\mathrm{coNP}$ にも属するならば、$\mathrm{NP} = \mathrm{coNP}$ であることを示してください。この結果は「$\mathrm{SAT}$ の充足不能性に短い証明書がある」という主張がどれほど強いかを教えてくれます。

解答

まず補題として、$\mathrm{coNP}$ が $\le_{\mathrm{p}}$ について閉じていること、すなわち「$A \le_{\mathrm{p}} B$ かつ $B \in \mathrm{coNP}$ ならば $A \in \mathrm{coNP}$」を示します。$f$ を $A \le_{\mathrm{p}} B$ の帰着関数とすると、定義 5.1 の条件 2 は $x \in A \iff f(x) \in B$ なので、その否定を取って $x \in \overline{A} \iff f(x) \in \overline{B}$ が成り立ちます。すなわち同じ $f$ が $\overline{A} \le_{\mathrm{p}} \overline{B}$ を与えます。$B \in \mathrm{coNP}$ は 注意 4.5 により $\overline{B} \in \mathrm{NP}$ を意味するので、定理 5.2 の 2 を $\overline{A} \le_{\mathrm{p}} \overline{B}$ に適用して $\overline{A} \in \mathrm{NP}$、すなわち $A \in \mathrm{coNP}$ を得ます。

本題に入ります。$B$ を NP 完全かつ $B \in \mathrm{coNP}$ とします。

$\mathrm{NP} \subseteq \mathrm{coNP}$：任意に $L \in \mathrm{NP}$ を取ります。$B$ は NP 困難なので 定義 6.1 より $L \le_{\mathrm{p}} B$ です。$B \in \mathrm{coNP}$ と上の補題より $L \in \mathrm{coNP}$ です。

$\mathrm{coNP} \subseteq \mathrm{NP}$：任意に $L \in \mathrm{coNP}$ を取ります。定義より $\overline{L} \in \mathrm{NP}$ で、いま示した包含より $\overline{L} \in \mathrm{coNP}$、すなわち $\overline{\overline{L}} = L \in \mathrm{NP}$ です。

以上より $\mathrm{NP} = \mathrm{coNP}$ です。

補足：$\mathrm{SAT}$ は NP 完全なので、もし「充足不能な CNF 論理式であることの多項式長の証明書」が見つかれば $\mathrm{SAT} \in \mathrm{coNP}$ となり、$\mathrm{NP} = \mathrm{coNP}$ が従います。命題論理の証明体系（導出原理など）に対する指数下界の研究は、まさにこの可能性を否定しにいく試みです。

参考文献

• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage Learning, 2013 — 第 7 章（時間計算量、$\mathrm{P}$、$\mathrm{NP}$、NP 完全性）、第 9 章（時間階層定理）。学部向けの標準的な入口です。
• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009 — 第 2 章（$\mathrm{NP}$ と NP 完全性）、第 3 章（対角線論法と相対化の壁）、第 23 章（自然証明）。証明の障壁まで扱う定番の大学院教科書です。
• Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979 — 巻末に約 300 個の NP 完全問題の一覧があります。
• Stephen A. Cook, “The complexity of theorem-proving procedures”, Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (STOC ‘71), 1971, pp. 151–158.
• Richard M. Karp, “Reducibility among combinatorial problems”, in Complexity of Computer Computations, Plenum Press, 1972, pp. 85–103.
• Theodore Baker, John Gill and Robert Solovay, “Relativizations of the P =? NP question”, SIAM Journal on Computing 4(4) (1975), 431–442.
• Clay Mathematics Institute, P vs NP Problem — ミレニアム懸賞問題の公式ページ。Cook による問題の公式記述が置かれています。

Appendix: Cook–Levin の定理の証明の骨格

定理 6.3 の NP 困難性の部分について、定理 6.3 の証明で述べた計算表の構成をもう少し詳しく書きます。完全な証明は Sipser 第 7 章または Arora–Barak 第 2 章にあります。

設定。 $L \in \mathrm{NP}$ とし、注意 4.2 の同値性により、$L$ を受理する非決定性 1 テープチューリング機械 $N$ と多項式 $T$ を取ります。$N$ は長さ $n$ の入力に対し、どの計算枝でも高々 $T(n)$ ステップで停止するとしてよく、また $T(n) \ge n$ としてよいものとします。$N$ の状態集合を $Q$、テープ記号の集合を $\Gamma$ とします。これらは有限で、$n$ に依存しません。

計算表。 入力 $x$（長さ $n$）に対する $N$ の 1 つの計算枝を、$(T(n)+1)$ 行 $\times$ $(T(n)+3)$ 列の表として書きます。第 $i$ 行は時刻 $i$ における「テープの内容と、ヘッド位置に状態記号を挿入したもの」を表し、両端には番兵記号を置きます。各マスに入る記号は $\Gamma \cup Q$ と番兵からなる有限集合 $\Delta$ の元です。時刻 $T(n)$ までしか動かないので、ヘッドが訪れるマスは初期位置から高々 $T(n)$ 個分に収まり、表の幅は $T(n)$ の 1 次式で足ります。

変数。 各マス $(i, j)$ と各記号 $s \in \Delta$ に対して命題変数 $x_{i,j,s}$ を用意し、「マス $(i,j)$ の中身が $s$ である」という意味を持たせます。変数の個数は $(T(n)+1)(T(n)+3)|\Delta| = O(T(n)^2)$ 個です（$|\Delta|$ は定数）。

4 種類の節。 求める論理式 $\varphi_x$ を、次の 4 群の節の論理積として定めます。

第 1 群（一意性）は、各マスの中身がちょうど 1 つに決まることを述べます。各 $(i,j)$ について $\bigvee_{s \in \Delta} x_{i,j,s}$ という節を 1 つと、$s \ne s'$ なる各対について $(\lnot x_{i,j,s} \lor \lnot x_{i,j,s'})$ を置きます。マスあたり $1 + \binom{|\Delta|}{2}$ 個、つまり定数個の節です。

第 2 群（開始）は、第 0 行が初期状況、すなわち番兵、初期状態 $q_0$、入力 $x$ の各文字、空白記号、番兵の順に並ぶことを、該当する変数を単一リテラルの節として並べることで述べます。$O(T(n))$ 個の節です。

第 3 群（遷移）は、連続する 2 行が $N$ の遷移規則と整合することを述べます。ここで効くのが「1 ステップで変化するのはヘッドの周囲だけ」という局所性です。第 $i$ 行の第 $j-1, j, j+1$ 列の 3 マスが決まれば、第 $i+1$ 行の第 $j$ 列に入り得る記号は $N$ の遷移規則から定まります。そこで各 $(i,j)$ について、上段 3 マスと下段 3 マスからなる $2 \times 3$ の窓の中身が「合法な窓」のいずれかに一致することを要求します。窓の中身の組合せは $|\Delta|^{6}$ 通りという定数個なので、合法でない組合せを禁止する節を定数個並べれば書けます。窓は $O(T(n)^2)$ 個なので、この群も $O(T(n)^2)$ 個の節です。

第 4 群（受理）は、表のどこかに受理状態が現れることを述べます。$N$ は受理したらその状況を保つように整えておけば、最終行を見るだけで済み、$\bigvee_{j} x_{T(n),j,q_{\mathrm{accept}}}$ という 1 個の節で書けます。

サイズと構成時間。 節の総数は $O(T(n)^2)$ です。第 1〜第 3 群の節はいずれも定数個のリテラルからなり、第 4 群の節だけが $O(T(n))$ 個のリテラルを持つので、リテラルの延べ個数も $O(T(n)^2)$ です。したがって $\varphi_x$ の記述長は $O(T(n)^2 \log T(n))$ 程度（変数の添字を書くビット数を含む）で、$n$ の多項式です。しかも各節は $x$ と $N$ の定義を見れば直接書き下せるので、$\varphi_x$ は $x$ から多項式時間で構成できます。

同値性。 $\varphi_x$ の充足割当は、第 1 群により表の各マスに記号を 1 つ割り当てるものと同一視でき、第 2・第 3 群によりその表は $N$ の $x$ に対する正しい計算の記録であり、第 4 群によりその計算は受理計算です。逆に、$N$ の $x$ に対する受理計算があれば、その計算表を読み取って作った割当は 4 群すべての節を満たします。したがって

$$x \in L \iff N \ \text{が} \ x \ \text{を受理する} \iff \varphi_x \ \text{は充足可能} \iff \langle \varphi_x \rangle \in \mathrm{SAT}$$

となり、$x \mapsto \langle \varphi_x \rangle$ が求める帰着です。$L$ は $\mathrm{NP}$ の任意の元だったので、$\mathrm{SAT}$ は NP 困難であり、例 4.4 の $\mathrm{SAT} \in \mathrm{NP}$ と合わせて NP 完全です。

なぜ SAT だったのか。 この証明を振り返ると、$\mathrm{SAT}$ が特別なのは「計算という動的な過程を、局所的な整合条件の連言として静的に書き下せる」からだと分かります。命題論理は計算のシミュレーションを表現するのにちょうど十分な表現力を持っており、しかも検証は多項式時間で終わります。この「表現力と検証容易性のつり合い」が、$\mathrm{SAT}$ を $\mathrm{NP}$ の中で最も難しい問題にしています。