この記事では、P、NP、NP完全、NP困難について、定義、具体例、および具体例がそのクラスに属することの証明を整理する。
用語
決定問題
入力に対して yes または no を返す問題のことを決定問題という。
言語
$\Sigma$ を記号の有限集合とする。
$\Sigma^* $ を $\Sigma$ 上のすべての有限文字列の集合とする。
このとき、 $\Sigma^* $ の部分集合を言語という。
L \subseteq \Sigma^*
決定問題は、「yesになる入力文字列だけを集めた集合」つまり言語として定式化することができる。
多項式時間帰着
$A$, $B$ を言語とする。$A$ から $B$ へ多項式時間帰着可能であるとは、
多項式時間で計算できる関数 $f$ が存在して、すべての入力 $x$ について次が成り立つことを意味する。
x \in A \iff f(x) \in B
$A$ から $B$ へ多項式時間帰着可能であることを $A \le_p B$ と書く。
直観的には、「$A$ を解くことは、入力を多項式時間で変換すれば $B$ を解くことに置き換えられる」という意味である。
P
定義
言語 $L$ が P に属するとは、ある決定性チューリング機械 $M$ と多項式 $p$ が存在して、任意の入力 $x$ に対して $M$ が高々 $p(|x|)$ ステップで停止し、次を満たすことである。
x \in L \text{ なら } M \text{ は受理する}
x \notin L \text{ なら } M \text{ は拒否する}
つまり、P は決定性計算で多項式時間に判定できる決定問題のクラスである。
具体例
有向グラフ到達可能性問題 PATH を考える。
PATH = \{\langle G,s,t\rangle \mid G \text{ において } s \text{ から } t \text{ へ到達可能}\}
入力は、有向グラフ $G=(V,E)$ と頂点 $s,t \in V$ である。問うことは、$s$ から $t$ への有向パスが存在するかである。
PATH が P に属することの証明
PATH を判定するアルゴリズムは次の通りである。
- 頂点 $s$ から幅優先探索または深さ優先探索を開始する
- 到達できる頂点をすべて記録する
- $t$ が到達済みなら yes、そうでなければ no と答える
隣接リスト表現を使えば、幅優先探索または深さ優先探索の計算時間は次の通りである。
O(|V| + |E|)
これは入力サイズに対する多項式時間である。したがって PATH は P に属する。
PATH \in P
NP
定義
言語 $L$ が NP に属するとは、ある多項式時間検証器 $V$ と多項式 $p$ が存在して、任意の入力 $x$ について次が成り立つことである。
x \in L \iff \exists y,\ |y| \le p(|x|) \land V(x,y)=1
ここで $y$ は証明書または witness と呼ばれる。
直観的には、NP は「yes であることの証拠を与えられたとき、その証拠が正しいことを多項式時間で検証できる問題」のクラスである。
NP は "not polynomial" ではない。NP は nondeterministic polynomial time の略である。
具体例
グラフ同型判定問題 GI を考える。
GI = \{\langle G,H\rangle \mid G \text{ と } H \text{ は同型である}\}
2 つの無向グラフ $G=(V_G,E_G)$、$H=(V_H,E_H)$ が同型であるとは、頂点集合の全単射 $\pi: V_G \to V_H$ が存在して、任意の $u,v \in V_G$ について次が成り立つことである。
\{u,v\} \in E_G \iff \{\pi(u),\pi(v)\} \in E_H
つまり、頂点名を付け替えるだけで同じグラフになる、ということである。
GI が NP に属することの証明
GI の証明書 $y$ として、頂点対応を表す写像 $\pi$ を与える。
検証器 $V$ は次を確認する。
- $\pi$ が $V_G$ から $V_H$ への全単射である
- 任意の頂点対 $u,v \in V_G$ について、辺の有無が保存されている
すなわち、次をすべて確認する。
\{u,v\} \in E_G \iff \{\pi(u),\pi(v)\} \in E_H
頂点数を $n$ とすると、確認すべき頂点対は高々 $n^2$ 個である。隣接行列を使えば、各辺の確認は定数時間でできる。したがって検証全体は多項式時間で終わる。
また、$G$ と $H$ が同型なら、同型写像 $\pi$ を証明書として与えれば検証器は受理する。逆に、検証器が受理する $\pi$ が存在するなら、その $\pi$ は同型写像である。
したがって GI は NP に属する。
GI \in NP
なお、GI が P に属するかどうかは現在知られていない。また、GI は NP完全とも知られていない。
NP完全
定義
言語 $C$ が NP完全であるとは、次の 2 条件を満たすことである。
- $C \in NP$
- 任意の $L \in NP$ について $L \le_p C$
2 つ目の条件は、$C$ が NP困難であることを意味する。
したがって、NP完全とは「NP に属する NP困難な問題」である。
C \text{ is NP-complete} \iff C \in NP \land \forall L \in NP,\ L \le_p C
具体例
充足可能性問題 SAT を考える。
SAT = \{\langle \varphi\rangle \mid \varphi \text{ は充足可能な命題論理式である}\}
ここで、命題論理式 $\varphi$ が充足可能であるとは、変数への真理値割当によって $\varphi$ 全体を真にできることである。
たとえば次の式は充足可能である。
(x_1 \lor \neg x_2) \land x_2
$x_1=true$、$x_2=true$ とすれば式全体が真になるからである。
一方、次の式は充足不能である。
x_1 \land \neg x_1
どのように $x_1$ に真理値を割り当てても、式全体を真にできないからである。
SAT が NP に属することの証明
SAT の証明書 $y$ として、式 $\varphi$ に現れる各変数への真理値割当を与える。
検証器は、その割当のもとで $\varphi$ を評価する。式のサイズを $n$ とすると、構文木を一度たどれば評価できるため、検証は多項式時間で終わる。
$\varphi$ が充足可能なら、$\varphi$ を真にする割当を証明書として与えれば検証器は受理する。逆に、検証器が受理する割当が存在するなら、$\varphi$ は充足可能である。
したがって SAT は NP に属する。
SAT \in NP
SAT が NP困難であることの証明
SAT が NP困難であることは Cook-Levin 定理によって示される。
Cook-Levin 定理は、任意の $L \in NP$ について、入力 $x$ から命題論理式 $\varphi_x$ を多項式時間で構成でき、次が成り立つことを述べる。
x \in L \iff \varphi_x \in SAT
$\varphi_x$ は、直感的には「$x$ の証明書 $y$ を検証器 $V$ が受理する」という処理の流れを命題論理式として表現したものである。
$L \in NP$ なので、検証器の計算時間は多項式時間である。そのため、計算履歴の長さも多項式で抑えられる。この計算履歴を表す論理式も多項式サイズで構成できる。
したがって、任意の $L \in NP$ について次が成り立つ。
L \le_p SAT
よって SAT は NP困難である。
SAT \text{ is NP-hard}
すでに $SAT \in NP$ を示したので、SAT は NP完全である。
SAT \text{ is NP-complete}
NP困難
定義
言語 $H$ が NP困難であるとは、任意の $L \in NP$ について次が成り立つことである。
L \le_p H
つまり、NP に属するすべての問題が、多項式時間で $H$ に帰着できるということである。
重要なのは、NP困難の定義では $H \in NP$ を要求しないことである。したがって、NP困難な問題は NP に属していてもよく、属していなくてもよい。
NP完全は、NP に属する NP困難問題である。
NP\text{-complete} = NP \cap NP\text{-hard}
具体例
停止問題 HALT を考える。
HALT = \{\langle M,w\rangle \mid M \text{ は入力 } w \text{ 上で停止する}\}
ここで $M$ はチューリング機械、$w$ はその入力である。
HALT は決定不能である。つまり、任意の $M,w$ について、$M$ が $w$ 上で停止するかどうかを常に正しく判定するアルゴリズムは存在しない。
したがって HALT は P にも NP にも属しない。P や NP は、少なくとも決定可能な問題のクラスだからである。
HALT が NP困難であることの証明
任意の $L \in NP$ を取る。
$L \in NP$ なので、多項式時間検証器 $V$ と多項式 $p$ が存在して、任意の入力 $x$ について次が成り立つ。
x \in L \iff \exists y,\ |y| \le p(|x|) \land V(x,y)=1
ここで、入力 $x$ からチューリング機械 $M_x$ を作る。
$M_x$ は次のように動作する。
- 長さ $p(|x|)$ 以下のすべての文字列 $y$ を順に列挙する
- 各 $y$ について $V(x,y)$ を実行する
- どれか 1 つでも $V(x,y)=1$ になれば停止する
- どの $y$ でも $V(x,y)=1$ にならなければ無限ループする
このとき、次が成り立つ。
x \in L \iff \langle M_x,\epsilon\rangle \in HALT
※ $\epsilon$ は空文字列
まず $x \in L$ なら、受理される証明書 $y$ が存在する。したがって $M_x$ はその $y$ を見つけた時点で停止する。
逆に $x \notin L$ なら、どの $y$ についても $V(x,y)=1$ にならない。したがって $M_x$ は停止せず、無限ループする。
また、$x$ から $M_x$ の記述を作る処理は、多項式時間で実行できる。$M_x$ の中に $x$ と検証器 $V$ を埋め込めばよいからである。
したがって、任意の $L \in NP$ について次が成り立つ。
L \le_p HALT
よって HALT は NP困難である。
HALT \text{ is NP-hard}
ただし HALT は決定不能なので NP には属しない。したがって HALT は NP完全ではない。
4 つのクラスの関係
ここまでの内容を整理すると、次のようになる。
| クラス | 定義 | 例 | 例である理由 |
|---|---|---|---|
| P | 決定性計算で多項式時間に判定できる | PATH | BFS または DFS で到達可能性を多項式時間に判定できる |
| NP | 多項式長の証明書を多項式時間で検証できる | GI | 同型写像を証明書として与えれば、辺の保存を多項式時間で確認できる |
| NP完全 | NP に属し、かつ NP のすべての問題から多項式時間帰着される | SAT | 真理値割当で検証でき、Cook-Levin 定理により任意の NP 問題から帰着される |
| NP困難 | NP のすべての問題から多項式時間帰着される | HALT | 任意の NP 検証器の「受理証明書が存在するか」を停止性に変換できる |
包含関係としては、次が成り立つ。
P \subseteq NP
NP\text{-complete} = NP \cap NP\text{-hard}
参考文献
- Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach
- Stephen Cook, The P versus NP Problem