計算可能性と NP 完全性チューリング機械・停止問題・P と NP・多項式時間帰着

チューリング機械で判定できる（必ず停止して正しく答える）問題を決定可能という。停止問題は対角線論法により決定不能で、ある問題 $A$ を別の問題 $B$ に帰着できれば、 $B$ が決定可能なら $A$ も決定可能である。計算量の側では、多項式時間で解ける問題のクラスを P、答えが yes のときに多項式長の証拠を多項式時間で検証できる問題のクラスを NP という。NP のすべての問題が多項式時間帰着できる NP の問題を NP 完全といい、SAT が最初の例である（クック・レビンの定理）。

計算理論の第2単元（全2単元）。先に読む単元：オートマトンと正規言語、アルゴリズムとデータ構造・計算量と漸化式

情報系院試の問題集・ロードマップ

東大情報理工・東京科学大・阪大の大学別に、出題マップと類題を1冊にした教材（各4,980円）。収録内容と見本を商品ページで確認できる。

情報系の教材を見る

チューリング機械と決定可能性の定義

定義

チューリング機械

チューリング機械は7つ組 $M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\mathrm{acc}}, q_{\mathrm{rej}})$ で、 $\Sigma$ は入力アルファベット、 $\Gamma \supseteq \Sigma \cup \{\sqcup\}$ はテープ記号（ $\sqcup$ は空白）、遷移関数は

\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}

である。片側に無限のテープ上でヘッドが記号を読み、書き換えて左右に1マス動く。 $q_{\mathrm{acc}}$ に入れば受理、 $q_{\mathrm{rej}}$ に入れば拒否して停止し、どちらにも入らなければ動き続ける。

定義

決定可能と認識可能

言語 $L$ について、 $L$ の文字列を受理し、それ以外では停止しないか拒否するチューリング機械があるとき、 $L$ を認識可能（帰納的可算）という。すべての入力で停止し、 $L$ の文字列だけを受理する機械があるとき、 $L$ を決定可能（帰納的）という。決定可能な言語は認識可能である。

多テープや非決定性のチューリング機械も、認識・決定できる言語のクラスは1テープ決定性の機械と同じである（計算時間は変わり得る）。「直観的に計算できる関数はチューリング機械で計算できる関数である」という主張をチャーチ・チューリングの提唱という。「計算できる」の直観的な意味を数学的な定義と結びつける主張なので、数学の定理として証明する対象ではない。

停止問題の決定不能性と帰着

定理・法則

停止問題の決定不能性

条件

$\langle M, w \rangle$ はチューリング機械 $M$ と入力 $w$ の符号化。 $\mathrm{HALT} = \{\langle M, w\rangle \mid M \text{ は } w \text{ で停止する}\}$ 。

主張

$\mathrm{HALT}$ は認識可能だが決定可能でない。

要点

決定する機械 $H$ があるとし、入力 $\langle M \rangle$ に対して「 $H$ が $\langle M, \langle M \rangle\rangle$ を受理すれば無限ループ、拒否すれば停止」する機械 $D$ を作る。 $D$ に $\langle D \rangle$ を与えると、 $D$ が停止するのは $D$ が停止しないときに限ることになり矛盾する。認識可能なことは、 $M$ を $w$ で模倣して停止したら受理すればよいことから分かる。

定理・法則

決定可能性と補集合

条件

言語 $L \subseteq \Sigma^*$ 、補集合 $\overline{L} = \Sigma^* \setminus L$ 。

主張

$L$ が決定可能であることと、 $L$ と $\overline{L}$ がともに認識可能であることは同値である。

要点

両方の認識機械を1ステップずつ交互に動かせば、どちらかが必ず受理して停止する。この定理から $\overline{\mathrm{HALT}}$ は認識可能でない。

定理・法則

写像帰着

条件

計算可能な全域関数 $f: \Sigma^* \to \Sigma^*$ で、すべての $w$ について $w \in A \iff f(w) \in B$ （ $A \le_m B$ と書く）。

主張

$B$ が決定可能なら $A$ も決定可能である。対偶をとると、 $A$ が決定不能なら $B$ も決定不能である。

要点

ある問題 $B$ の決定不能性を示すには、決定不能と分かっている $A$ （停止問題など）から $B$ へ帰着する。向きを逆にして $B \le_m A$ を示しても何も言えない。

P・NP・NP 完全の定義とクック・レビンの定理

定義

P と NP

決定性チューリング機械がある多項式 $p$ について $O(p(n))$ 時間で決定できる言語のクラスを P という。言語 $L$ が NP に属するとは、多項式 $q$ と多項式時間の検証アルゴリズム $V$ があって

x \in L \iff \exists c\ \bigl(|c| \le q(|x|) \text{ かつ } V(x, c) = 1\bigr)

となることをいう。 $c$ を証拠（証明書）と呼ぶ。同値な定義として、非決定性チューリング機械が多項式時間で決定できる言語のクラスでもある。 $\mathrm{P} \subseteq \mathrm{NP}$ は成り立つが、 $\mathrm{P} = \mathrm{NP}$ かどうかは未解決である。

定義

多項式時間帰着・NP 困難・NP 完全

多項式時間で計算できる $f$ で $x \in A \iff f(x) \in B$ となるとき、 $A \le_p B$ と書く。NP のすべての言語 $A$ について $A \le_p B$ となる $B$ を NP 困難、さらに $B \in \mathrm{NP}$ なら NP 完全という。NP 困難な問題は NP に属さなくてもよい（停止問題も NP 困難である）。

定理・法則

クック・レビンの定理

条件

SAT は、論理式が充足可能（変数への真偽の割り当てで真にできる）かを問う問題。

主張

SAT は NP 完全である。節の長さを3に限った 3SAT も NP 完全である。

要点

NP の言語を決定する非決定性チューリング機械の多項式時間の計算を、テープの内容・状態・ヘッド位置を表す変数の論理式で書き下す。2SAT（節の長さ2）は P に属する。

定理・法則

NP 完全性の示し方

条件

$A$ は NP 完全と分かっている問題、 $B$ は対象の問題。

主張

$B \in \mathrm{NP}$ であり、 $A \le_p B$ なら、 $B$ は NP 完全である。

要点

$\le_p$ は推移的なので、NP のすべての $L$ について $L \le_p A \le_p B$ 。 $B$ のどれか1つが多項式時間で解ければ $\mathrm{P} = \mathrm{NP}$ になる。

代表的な NP 完全問題と関係

帰着の例: $\mathrm{SAT} \le_p \mathrm{3SAT} \le_p \mathrm{INDEPENDENT\text{-}SET} \le_p \mathrm{VERTEX\text{-}COVER}$
独立集合と頂点被覆: $S \text{ が独立集合} \iff V \setminus S \text{ が頂点被覆}, \qquad \alpha(G) + \tau(G) = |V|$
$\alpha$ は最大独立集合の大きさ、 $\tau$ は最小頂点被覆の大きさ。
独立集合とクリーク: $S \text{ が } G \text{ の独立集合} \iff S \text{ が補グラフ } \overline{G} \text{ のクリーク}$
その他の NP 完全問題: $\text{ハミルトン閉路},\ \text{3彩色},\ \text{部分和},\ \text{巡回セールスマン（判定版）}$

帰着と検証の計算例

計算例

3SAT から独立集合への帰着

$\varphi = (x_1 \lor x_2 \lor \lnot x_3) \land (\lnot x_1 \lor x_2 \lor x_3) \land (x_1 \lor \lnot x_2 \lor \lnot x_3)$ に対して、独立集合問題のグラフ $G$ と目標 $k$ を作り、 $\varphi$ の充足可能性と対応させよ。

解答

節ごとに3つのリテラルを頂点とし（計 $3 \times 3 = 9$ 頂点）、次の辺を張る。

同じ節の3頂点を三角形で結ぶ（ $3 \times 3 = 9$ 本）。
異なる節にある $x_i$ と $\lnot x_i$ を結ぶ（ $x_1$ – $\lnot x_1$ が2本、 $x_2$ – $\lnot x_2$ が2本、 $x_3$ – $\lnot x_3$ が2本の計6本）。

$k$ を節の数 $3$ とする。三角形から1頂点ずつしか選べないので、大きさ3の独立集合は各節から1つずつ、矛盾しないリテラルを選ぶことに当たる。 $x_1 = x_2 = \text{真}$ 、 $x_3 = \text{偽}$ はすべての節を真にし、第1節の $x_1$ 、第2節の $x_2$ 、第3節の $\lnot x_3$ が大きさ3の独立集合になる。

検算

全 $2^9$ 通りの頂点集合を調べると最大独立集合の大きさは3で、 $k = 3$ に一致する。 $2^3 = 8$ 通りの割り当てのうち5通りが $\varphi$ を満たす。グラフの辺は $9 + 6 = 15$ 本で、構成は節の数の多項式時間でできる。

計算例

独立集合と頂点被覆の補集合関係

頂点 $\{1,2,3,4,5\}$ 、辺 $\{12, 13, 23, 34, 45\}$ のグラフで、最大独立集合と最小頂点被覆の大きさを求めよ。

解答

三角形 $\{1,2,3\}$ からは独立集合に1頂点しか入らず、残りの $\{4, 5\}$ も隣接するので1頂点しか入らない。よって $\alpha \le 2$ で、 $\{1, 4\}$ は独立集合だから $\alpha = 2$ 。補集合 $\{2, 3, 5\}$ は頂点被覆で、 $\tau = 5 - 2 = 3$ 。

検算

$\{2, 3, 5\}$ は5本の辺 $12, 13, 23, 34, 45$ のすべてで少なくとも一端を含む。 $2^5 = 32$ 通りすべての部分集合で「 $S$ が独立集合 $\iff$ $V \setminus S$ が頂点被覆」を確かめ、 $\alpha = 2$ 、 $\tau = 3$ を得た。

計算例

部分和問題が NP に属すること

整数の集合 $\{3, 34, 4, 12, 5, 2\}$ と目標 $T = 9$ の部分和問題について、証拠と検証の方法を述べよ。

解答

証拠は和が $T$ になる部分集合で、たとえば $\{4, 5\}$ 。検証は、証拠の各要素が元の集合にあることと和が $T$ に等しいことを確かめればよく、入力長の多項式時間で終わる。よって部分和問題は NP に属する。

検算

全部分集合を調べると、和が9になるのは $\{4, 5\}$ と $\{3, 4, 2\}$ の2つ。動的計画法は $O(nT)$ で解くが、 $T$ の桁数に対して指数時間なので、部分和問題が P に属することを示したことにはならない。

答案でよくある誤り

1
NP を「多項式時間で解けない問題」と説明する。NP は非決定性多項式時間（yes の証拠を多項式時間で検証できる）の略で、P も NP に含まれる。
2
帰着の向きを逆にする。 $B$ が NP 困難であることを示すには、既知の NP 完全問題 $A$ から $A \le_p B$ を作る。 $B \le_p A$ は $B$ が $A$ より難しくないことしか言わない。
3
NP 完全性の証明で $B \in \mathrm{NP}$ を示し忘れる。帰着だけでは NP 困難までで、検証アルゴリズムを書いて NP に属することも示す。
4
帰着で「 $x \in A \Rightarrow f(x) \in B$ 」の一方向だけ示す。逆向き $f(x) \in B \Rightarrow x \in A$ と、 $f$ が多項式時間で計算できることも示す。
5
停止問題を「どんなプログラムも停止するか判定できない」と述べる。決定不能なのは、すべての $\langle M, w\rangle$ を正しく判定する1つの機械が存在しないことで、個々の機械について停止を示せる場合はある。
6
擬多項式時間の $O(nW)$ を見て、ナップサック問題が P に属すると書く。 $W$ は桁数に対して指数的に大きくなり得るので、多項式時間ではない（動的計画法と貪欲法）。