P対NP問題
概要
P対NP問題（P versus NP problem）とは、多項式時間で判定できる言語のクラス $\mathrm{P}$ と、多項式の長さの証明書を多項式時間で確かめられる言語のクラス $\mathrm{NP}$ が一致するかを問う、計算量の理論の未解決問題であり、Clay 数学研究所のミレニアム懸賞問題の 1 つである。$\mathrm{P}\subset\mathrm{NP}\subset\mathrm{EXP}$ が成り立ち、充足可能性の問題などの NP完全な問題が 1 つでも多項式時間で解ければ $\mathrm{P}=\mathrm{NP}$ となる。$\mathrm{P}=\mathrm{NP}$ なら証明書そのものも多項式時間で見つけられ、$\mathrm{NP}=\mathrm{coNP}$ も従う。対角線論法の議論の相対化や回路の下界の難しさが障壁として知られている。
P 対 NP 問題（P versus NP problem）は、「答えが『はい』であることの短い証拠を効率よく確かめられる問題は、すべて効率よく解けるか」という問いである。効率よく解ける判定問題の全体をクラス P、短い証拠を効率よく確かめられる判定問題の全体をクラス NP とすると、P $\subset$ NP はすぐに分かり、問題は P $=$ NP かどうかである。Clay 数学研究所のミレニアム懸賞問題の 1 つであり、未解決である（CJW06 S. Cook「The P versus NP Problem」§1, p. 88）。
グラフが Hamilton 閉路をもつか、論理式を真にする値の割り当てがあるか、といった多くの問題は NP に属し、しかも NP の中で最も難しい（NP完全）。P $\ne$ NP が正しければ、これらの問題を多項式時間で解く方法はない。逆に P $=$ NP なら、判定だけでなく証拠そのものも多項式時間で見つけられる。
この記事では、P・NP・coNP・EXP を定義して包含関係 P $\subset$ NP $\subset$ EXP を示し、P $=$ NP のときに証拠の探索が多項式時間でできること、P $=$ NP なら NP $=$ coNP であること、NP完全な問題が coNP に属すれば NP $=$ coNP であることを証明する。最後に、この問題を解こうとする方法に知られている障壁を、所在を挙げて紹介する。NP完全性の理論（多項式時間還元、Cook–Levin の定理、個々の問題の NP完全性）は NP完全 の記事で扱う。
定義
アルファベット $\Sigma$ は 2 個以上の記号からなる有限集合とし、$\Sigma$ の記号の有限列（語）全体を $\Sigma^*$、語 $w$ の長さを $\lvert w\rvert$ と書く。$\Sigma^*$ の部分集合を $\Sigma$ 上の言語という。判定問題は「答えが『はい』になる入力の全体」という言語として扱う。言語 $L\subset\Sigma^*$ の補集合を $\overline L:=\Sigma^*\setminus L$ と書く。
Turing 機械 $M$ が言語 $L$ を時間 $T$ で判定するとは、すべての $w\in\Sigma^*$ について $M$ が入力 $w$ で $T(\lvert w\rvert)$ ステップ以内に停止し、受理状態で停止することと $w\in L$ が同値であることをいう。機械・受理・ステップ数の正確な定義は NP完全 の定義「言語を判定する機械と計算時間」に従う。
- ある自然数 $c\ge1$ について時間 $n^c+c$ で $L$ を判定する Turing 機械があるとき、$L\in\mathrm{P}$ という。
- 言語 $L\subset\Sigma^*$ が NP に属するとは、アルファベット $\Sigma_1$、$\Sigma\cup\Sigma_1$ に属さない記号 $\#$、自然数 $c\ge1$、P に属する言語 $R$ があって、すべての $w\in\Sigma^*$ について
$$ w\in L\iff\text{ある }y\in\Sigma_1^*\text{ で }\lvert y\rvert\le\lvert w\rvert^c+c\text{ かつ }w\#y\in R $$
が成り立つことをいう。$y$ を $w$ の証明書、$R$ を検証の言語という。 - $\overline L\in\mathrm{NP}$ となる言語 $L$ の全体を coNP と書く。
- ある $c\ge1$ について時間 $2^{n^c+c}$ で $L$ を判定する Turing 機械があるとき、$L\in\mathrm{EXP}$ という。
1 と 2 は NP完全 の定義「クラス P と NP」と同じであり、CJW06 §1（pp. 87–88）の定義と同じ形である。
P $=$ NP であるかどうかを決定する問題を P 対 NP 問題 という。P $\ne$ NP であるという予想を P $\ne$ NP 予想 という。
Turing 機械を、複数のテープをもつ機械や通常のプログラムに替えても、計算時間は多項式の範囲でしか変わらないので、P・NP・coNP・EXP はこうした計算のモデルの選び方によらない（MSm24 Theorem 6.1.2, p. 198・Theorem 6.2.2, p. 199。CJW06 p. 87。この記事では証明しない）。以下の証明では、この事実により手続きを通常のプログラムの形で書き、その実行時間を数える。
数を 10 進法で書いた語で表す。
- 平方数の全体は P に属する（CJW06 p. 89）。
- 合成数の全体は NP に属する。$a$ が合成数であることの証明書は、$1< b< a$、$b\mid a$ を満たす $b$ であり、$\lvert b\rvert\le\lvert a\rvert$ で、割り算は多項式時間でできる。合成数の全体は実は P にも属する（Agrawal–Kayal–Saxena による。CJW06 p. 89 による紹介。この記事では証明しない）。
- Hamilton 閉路をもつ有限グラフの全体は NP に属する。証明書は閉路をなす頂点の並びで、辺がつながっていることは多項式時間で確かめられる。この言語は NP完全である（Hamilton閉路 の注意「判定の難しさ」、NP完全 の節「ほかの NP完全問題」）。
- Hamilton 閉路をもたないグラフを表す語の全体は coNP に属する（補集合は、グラフを正しく表していない語と Hamilton 閉路をもつグラフを表す語からなり、NP に属する）。これが NP に属するかどうかは知られていない。属するなら、後の thm-pnp-conp の 2 により NP $=$ coNP となる。
包含関係
- P は補集合をとる操作で閉じている。すなわち $L\in\mathrm{P}$ なら $\overline L\in\mathrm{P}$ である。EXP も同様である。
- $\mathrm{P}\subset\mathrm{NP}\cap\mathrm{coNP}$ である。
- $\mathrm{NP}\subset\mathrm{EXP}$、$\mathrm{coNP}\subset\mathrm{EXP}$ である。
1：$L$ を時間 $T$ で判定する機械 $M$ をとる。$M$ に新しい状態 $q'$ を加え、受理状態 $q_{\mathrm{acc}}$ 以外のどの状態 $q$ と記号 $a$ についても、$M$ で遷移が定義されていなければ「$a$ をそのまま書き、ヘッドを動かさず、状態 $q'$ に移る」遷移を加え、$q'$ を新しい受理状態とする。$q_{\mathrm{acc}}$ からの遷移はないので、もとの機械が受理した入力では新しい機械は $q_{\mathrm{acc}}$ で停止して拒否し、もとの機械が拒否した入力では 1 ステップ後に $q'$ で停止して受理する。どの入力でも時間 $T+1$ 以内に停止するので、$\overline L$ は時間 $T+1$ で判定される。$T$ が多項式（または $2^{n^c+c}$ の形）なら $T+1$ も同じ形の上界をもつ。
2：$L\in\mathrm{P}$ なら、証明書を使わず $R:=\{w\#y:w\in L\}$ とすれば $L\in\mathrm{NP}$ である（$R$ は $\#$ より前の部分を $L$ の判定機械で調べればよいので P に属する）。1 により $\overline L\in\mathrm{P}\subset\mathrm{NP}$ なので $L\in\mathrm{coNP}$ でもある。
3：$L\in\mathrm{NP}$ とし、定義の $\Sigma_1,c,R$ をとる。$R$ を時間 $n^d+d$ で判定する機械をとる。入力 $w$（$n:=\lvert w\rvert$）に対し、長さ $p(n):=n^c+c$ 以下のすべての $y\in\Sigma_1^*$ について $w\#y\in R$ を調べ、1 つでも成り立てば受理する。$y$ の個数は $s:=\lvert\Sigma_1\rvert$ として $\sum_{j=0}^{p(n)}s^j\le(s+1)^{p(n)}$ 以下であり、1 つの $y$ の検査は $(n+1+p(n))^d+d$ ステップ程度で済むので、全体の時間はある多項式 $q$ について $2^{q(n)}$ で抑えられる（同じ議論が MSm24 Theorem 6.3.8, p. 210 にある）。よって $L\in\mathrm{EXP}$ である。$L\in\mathrm{coNP}$ なら $\overline L\in\mathrm{NP}\subset\mathrm{EXP}$ なので、1 により $L\in\mathrm{EXP}$ である。$\square$
P $\ne$ EXP であること、すなわち指数時間で判定できるが多項式時間では判定できない言語があることは知られている（MSm24 §6.3.3, p. 211。この記事では証明しない）。これと thm-pnp-inclusions から、次がすぐに分かる。
P $\ne$ NP と NP $\ne$ EXP の少なくとも一方が成り立つ。
P $=$ NP かつ NP $=$ EXP なら P $=$ EXP となり、P $\ne$ EXP に反する。$\square$
どちらが成り立つのか（あるいは両方か）は知られていない。
$\mathrm{P}=\mathrm{NP}$ の言い換えと帰結
NP完全 の命題「還元の基本性質」の 4 により、NP完全な言語 $B$ について、$B\in\mathrm{P}$ と P $=$ NP は同値である。同じ記事の定理「Cook–Levin の定理」により充足可能性の問題 SAT は NP完全なので、P 対 NP 問題は「SAT は多項式時間で判定できるか」という 1 つの具体的な問いと同じである。対偶をとると、P $\ne$ NP なら Hamilton 閉路の有無も含め、どの NP完全な問題も多項式時間では判定できない。
P $=$ NP ならば、判定ができるだけでなく、証明書を実際に見つけることもできる。
P $=$ NP と仮定する。$L\in\mathrm{NP}$ とし、定義の $\Sigma_1,\#,c,R$ をとり、$p(n):=n^c+c$ とする。このとき、入力 $w$ に対し、$w\in L$ なら $\lvert y\rvert\le p(\lvert w\rvert)$ かつ $w\#y\in R$ を満たす $y$ を出力し、$w\notin L$ ならそのことを出力する手続きで、多項式時間で動くものがある。
段 1（接頭辞の言語）。 $\Sigma\cup\Sigma_1\cup\{\#\}$ に属さない新しい記号 $\diamond$ を使い、
$$
L':=\bigl\{w\#u:\ u\in\Sigma_1^*,\ \text{ある }v\in\Sigma_1^*\text{ で }\lvert uv\rvert\le p(\lvert w\rvert)\text{ かつ }w\#uv\in R\bigr\}
$$
とおく（$w\in\Sigma^*$ とし、この形でない語は $L'$ に属さないとする）。$L'$ は NP に属する。実際、証明書を $v$、検証の言語を $R':=\{w\#u\diamond v:\lvert uv\rvert\le p(\lvert w\rvert),\ w\#uv\in R\}$ とすればよい。$R'$ は、長さを比べてから記号 $\diamond$ を取り除いて $R$ の判定機械にかければ判定でき、P に属する。また $\lvert v\rvert\le p(\lvert w\rvert)\le p(\lvert w\#u\rvert)$ である。仮定 P $=$ NP により $L'\in\mathrm{P}$ である。
段 2（1 文字ずつ延ばす）。 入力 $w$ に対し、次の手続きを行う。まず $w\#\in L'$（$u$ が空の場合）を調べ、成り立たなければ「$w\notin L$」と出力する。成り立てば $u:=$ 空の語とし、次をくり返す。
- $w\#u\in R$ なら $u$ を出力して終わる。
- そうでなければ、$w\#ua\in L'$ となる $a\in\Sigma_1$ を 1 つ見つけ、$u:=ua$ とする。
段 3（正しさ）。 $L$ の定義により、$w\in L$ と $w\#\in L'$ は同値なので、最初の出力は正しい。くり返しの間 $w\#u\in L'$ が保たれる。実際、$w\#u\in L'$ を示す $v$ をとると、$w\#u\notin R$ なら $v$ は空でなく、その最初の文字 $a$ について $w\#ua\in L'$ となる。よって 2 つめの場合の $a$ はつねに見つかる。$w\#u\in L'$ なので $\lvert u\rvert\le p(\lvert w\rvert)$ であり、$u$ はくり返すたびに 1 文字長くなるから、くり返しは高々 $p(\lvert w\rvert)+1$ 回で終わり、そのとき出力した $u$ は $\lvert u\rvert\le p(\lvert w\rvert)$、$w\#u\in R$ を満たす。
段 4（時間）。 各回で調べる語の長さは $\lvert w\rvert+2+p(\lvert w\rvert)$ 以下であり、$R$ と $L'$ の判定はその長さの多項式時間で済む。1 回あたりの判定は高々 $\lvert\Sigma_1\rvert+1$ 回、回数は高々 $p(\lvert w\rvert)+1$ なので、全体は $\lvert w\rvert$ の多項式時間である。$\square$
SAT の場合、この手続きは変数を 1 つずつ真または偽に固定し、充足可能性が保たれる方を選んでいくことにあたる（CJW06 p. 93）。
NP と coNP
$A\le_{\mathrm p}B$（NP完全 の定義「多項式時間還元・NP困難・NP完全」）で $B\in\mathrm{NP}$ なら、$A\in\mathrm{NP}$ である。
還元の写像 $f$ を時間 $\lvert w\rvert^d+d$ で計算する機械をとり、$B$ の定義の $\Sigma_1,\#,c,R_B$ をとる。NP完全 の補題「出力の長さと機械の連結」の 1 により $\lvert f(w)\rvert\le\lvert w\rvert+\lvert w\rvert^d+d+1$ である。$R_A:=\{w\#y:\ \lvert y\rvert\le\lvert f(w)\rvert^c+c\text{ かつ }f(w)\#y\in R_B\}$ とおくと、$R_A$ は $f(w)$ を計算し、$y$ の長さを $\lvert f(w)\rvert^c+c$ と比べてから $f(w)\#y$ を $R_B$ の判定機械にかければ判定でき、P に属する。そして
$$
w\in A\iff f(w)\in B\iff\text{ある }y\text{ で }\lvert y\rvert\le\lvert f(w)\rvert^c+c\text{ かつ }w\#y\in R_A
$$
である。$\lvert f(w)\rvert^c+c$ は $\lvert w\rvert$ の多項式で抑えられるので、すべての $w$ で $\lvert f(w)\rvert^c+c\le\lvert w\rvert^e+e$ となる自然数 $e$ がとれる。$R_A$ は長さの条件を含むので、右辺の「$\lvert y\rvert\le\lvert f(w)\rvert^c+c$」を「$\lvert y\rvert\le\lvert w\rvert^e+e$」に替えても同値は保たれ、$A\in\mathrm{NP}$ である。$\square$
- P $=$ NP なら NP $=$ coNP である。対偶をとると、NP $\ne$ coNP なら P $\ne$ NP である。
- NP完全な言語 $B$ が coNP に属するなら、NP $=$ coNP である。
1：P $=$ NP とする。$L\in\mathrm{coNP}$ なら $\overline L\in\mathrm{NP}=\mathrm{P}$ であり、thm-pnp-inclusions の 1 により $L\in\mathrm{P}=\mathrm{NP}$ である。逆に $L\in\mathrm{NP}=\mathrm{P}$ なら $\overline L\in\mathrm{P}=\mathrm{NP}$ なので $L\in\mathrm{coNP}$ である。
2：$B\subset\Delta^*$ を NP完全とし、$\overline B\in\mathrm{NP}$ とする。$A\subset\Sigma^*$ を coNP の任意の言語とすると、$\overline A\in\mathrm{NP}$ なので、還元の写像 $f$ で $w\in\overline A\iff f(w)\in B$ となるものがある。この $f$ について $w\in A\iff w\notin\overline A\iff f(w)\notin B\iff f(w)\in\overline B$ なので $A\le_{\mathrm p}\overline B$ であり、lem-pnp-reduction により $A\in\mathrm{NP}$ である。よって $\mathrm{coNP}\subset\mathrm{NP}$ である。$L\in\mathrm{NP}$ なら $\overline L\in\mathrm{coNP}\subset\mathrm{NP}$ なので $L\in\mathrm{coNP}$ であり、$\mathrm{NP}\subset\mathrm{coNP}$ も成り立つ。$\square$
NP $\ne$ coNP も未解決の予想である（CJW06 p. 93）。2 により、NP完全な問題の補集合が NP に属することは、NP $=$ coNP を意味する。
正の整数の組を表す語の言語
$$
L_{\mathrm{fact}}:=\{\langle a,b\rangle:\ 1< d< a\text{ かつ }d\mid b\text{ となる整数 }d\text{ がある}\}
$$
を考える（CJW06 p. 93）。$d$ が証明書なので $L_{\mathrm{fact}}\in\mathrm{NP}$ である。$b$ の素因数分解を証明書にすると補集合も NP に属する。各因数が素数であることは、素数の全体（2 以上で合成数でない数の全体）が P に属すること（ex-pnp-examples の 2）により多項式時間で確かめられ、積が $b$ であること、すべての素因数が $a$ 以上であることも多項式時間で確かめられるからである。よって $L_{\mathrm{fact}}\in\mathrm{NP}\cap\mathrm{coNP}$ であり、thm-pnp-conp の 2 により、$L_{\mathrm{fact}}$ が NP完全なら NP $=$ coNP となる。一方、$L_{\mathrm{fact}}$ に何回か問い合わせれば $b$ の最小の素因数が二分探索で求まるので（CJW06 p. 93）、$L_{\mathrm{fact}}\in\mathrm{P}$ なら素因数分解が多項式時間でできる。このため $L_{\mathrm{fact}}$ は、P にも NP完全にも属さないと考えられている NP の言語の例とされる（CJW06 p. 93）。
解決を阻んでいるもの
この節の結果はどれもこの記事では証明しない。所在は CJW06 の Cook の解説である。
- 相対化。 Turing 機械に、決まった言語 $A$ について「$x\in A$ か」を 1 ステップで答える装置（オラクル）を付けたものを考え、これを使って定めたクラスを $\mathrm{P}^A$、$\mathrm{NP}^A$ と書く。Baker–Gill–Solovay は $\mathrm{P}^A=\mathrm{NP}^A$ となるオラクル $A$ があることを示し、一方「一般的な」オラクル $B$ については $\mathrm{P}^B\ne\mathrm{NP}^B$ となる（CJW06 pp. 98–99）。停止問題の決定不能性を示すような対角線論法と還元を組み合わせた議論は、オラクルを付けてもそのまま通用する（相対化する）ので、それだけでは P と NP を分けられないと考えられている（CJW06 p. 98）。
- 回路の下界。 $\{0,1\}$ 上の言語が P に属すれば、入力の長さ $n$ ごとに大きさが $n$ の多項式の論理回路の族でその言語を計算できる（CJW06 p. 99）。したがって、ある NP の言語、たとえば 3-充足可能性について、回路の大きさが多項式で抑えられないことを示せば P $\ne$ NP が従う。単調な回路や段数を制限した回路については指数関数の下界が示されているが、制限のない回路について具体的な関数に示された下界は線形の程度にとどまる（CJW06 p. 99）。Razborov–Rudich は、それまでの下界の証明の多くが「自然な証明」という型に属し、強い擬似乱数生成器が存在するという予想のもとでは、この型の証明で一般の回路の強い下界を示すことはできないことを指摘した（CJW06 p. 99）。
- P $=$ NP の帰結。 P $=$ NP なら、素因数分解の困難さに頼る暗号は安全でなくなり（CJW06 pp. 93–94）、多項式時間で確かめられる形式的な証明については、長さが現実的な範囲の証明を機械が見つけられることになる（CJW06 p. 94。thm-pnp-search を、形式的な証明を証明書とする NP の言語に使う）。
反例：条件を外したとき
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 証明書の長さが多項式で抑えられる（def-pnp-classes の 2） | 長さの制限をなくし、$R:=\{1^e;1^x\#1^s: M_e\text{ は入力 }x\text{ で }s\text{ ステップ以内に停止する}\}$ | クラスが P と一致するかが未解決であること（P と異なることが証明できる） |
| 検証の言語が P に属する（def-pnp-classes の 2） | $R:=\{x\#:x\in H\}$（$H$ は停止集合を表す言語。証明書は空の語） | 同上 |
| 判定する機械がすべての入力で停止する（thm-pnp-inclusions の 1） | 半決定可能な言語の全体と、停止集合 $H$ | 補集合をとる操作で閉じること |
停止問題 の定義「停止問題」の停止集合 $H_0\subset\mathbb{N}^2$ を語で書いて、$H:=\{1^e;1^x:(e,x)\in H_0\}$ とする（$;$ は $1$ とも $\#$ とも異なる記号。$M_e$ は番号 $e$ の機械）。$H$ を判定する機械からは $H_0$ の特性関数を計算する機械が作れるので、停止問題 の定理「停止問題の決定不能性」により $H$ は決定可能でなく、とくに P に属さない。
各行の確かめを開く
1 行目：$x\in H$ であることと、ある $s$ で $x\#1^s\in R$ となることは同値である（停止問題 の補題「計算の記録と停止」と同じ考え方）。$R$ は $M_e$ を入力 $x$ で $s$ ステップだけ動かせば判定でき、その時間は入力 $1^e;1^x\#1^s$ の長さの多項式で抑えられるので、$R\in\mathrm{P}$ である。外したのは証明書の長さの制限だけだが、定まるクラスは $H\notin\mathrm{P}$ を含むので P と異なる。
2 行目：証明書の長さの上界（$0$）は満たすが、$R$ は P に属さない（$R$ が決定可能なら $H$ も決定可能になる）。定まるクラスは $H$ を含み、P と異なる。
3 行目：$H$ は半決定可能だが（停止問題 の定理「停止集合は半決定可能」）、その補集合は半決定可能でない（同記事の系「停止しない側は半決定可能でない」）。prf-pnp-inclusions の 1 の作り方は、停止しない入力では何も変えないので、すべての入力で停止しない機械には使えない。
補足
- 計算のモデル。 乱数を使う多項式時間の算法で判定できる言語のクラス BPP や、量子計算機のモデルとの関係も研究されている。Shor は量子計算機で素因数分解が多項式時間でできることを示した（CJW06 p. 91）。
- アルファベットの大きさ。 アルファベットが 2 文字以上なら、どの有限アルファベットの語も 2 文字の語で効率よく符号化できるので、問題の答えはアルファベットの選び方によらない（CJW06 p. 88）。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
