Cook–Levinの定理(Cook–Levin theorem)とは、論理式の充足可能性の問題 SAT が NP完全である、という定理である。多項式時間の検証の計算全体を時刻とマスの表に書くと、表の正しさは隣り合う 3 マスの局所的な整合性の連言になり、$O(T^2)$ 個の節で表せる。分割によって各節のリテラルを 3 個以下にしても NP完全であり、一方 2 個以下なら多項式時間で判定できる。
Cook–Levin の定理(Cook–Levin theorem)は、論理式の充足可能性の問題 SAT が NP完全であるという定理である。短い証明書を効率よく検証できる問題は、どれも「ある論理式を真にする割り当てがあるか」という 1 つの問いに書き直せる。
証明の核は 計算の局所性 である(AB07 §2.3 の見出し、p. 44)。Turing 機械の 1 ステップでは、テープの 1 マスの近くしか変わらない。計算全体を時刻とマスの表(タブロー)に書くと、表が正しい計算であることは、隣り合う 3 マスとその真下の 1 マスの整合性の連言になる。各整合性は有限の表で決まるので、一定の幅の節で書ける。
1971 年に Cook が NP完全の概念を導入して SAT の NP完全性を示し、同じ頃 Levin が独立に探索問題の形で同様の結果を得た。その後 Karp が 21 個の問題の NP完全性を示した(AB07 p. 44、章末の注 p. 61。CJW06 pp. 91–92)。
この記事では、Turing 機械の定義を短く置いたうえで、SAT の NP完全性を節の個数まで数えて証明し、3SAT への帰着を与える。この証明は節数が時間の 2 乗で済む形にしてあり、NP完全 の証明(ヘッドと状態を別の変数で表す形)とは符号化が異なる。
Turing 機械は Turing機械 の定義「Turing 機械」に従い、$M=(Q,\Gamma,\sqcup,q_0,\delta)$ と書く。$Q$ は状態の有限集合、$\Gamma$ はテープ記号の有限集合、$\sqcup\in\Gamma$ は空白、$\delta\colon Q\times\Gamma\rightharpoonup Q\times\Gamma\times\{-1,0,1\}$ は 部分写像 である。$\delta(q,a)=(q',b,\epsilon)$ は「状態 $q$ で記号 $a$ を読んだら、$b$ を書き、ヘッドを $\epsilon$ だけ動かし、状態 $q'$ に移る」を表す(同記事の $\mathrm{L},\mathrm{R},\mathrm{N}$ を $-1,1,0$ と書いた)。テープは $\mathbb{Z}$ で添字づけられ、有限個のマスを除いて空白である。様相 は状態 $q$、テープ $\tau\colon\mathbb{Z}\to\Gamma$、ヘッドの位置 $h$ の組 $(q,\tau,h)$ で、$\delta(q,\tau(h))$ が定義されていなければ 停止様相 である。定義されていれば次の様相がただ 1 つ決まる。
語 $u$ を入力とする 初期様相 は、状態 $q_0$、ヘッドの位置 $0$、テープのマス $0,1,\dots$ に $u$ を書いたものである。
受理状態 $q_{\mathrm{acc}}$($\delta(q_{\mathrm{acc}},\cdot)$ はどこでも定義されない)を指定した機械を考える。
これは NP完全 の定義と同じである。還元の推移性や、NP完全な言語が P に属することと P $=$ NP の同値は、同記事の命題「還元の基本性質」で示されている。
変数 $x$ とその否定 $\neg x$ を リテラル という。リテラルの空でない有限集合を 節 といい、節の有限列を 連言標準形(CNF)の論理式という。真偽の割り当て $\nu$ が論理式を 充足する とは、どの節も $\nu$ で真になるリテラルを含むことをいう。充足する割り当てをもつ CNF の論理式(を符号化した語)全体を SAT、どの節もリテラルが高々 3 個である論理式に限ったものを 3SAT と書く。
変数の割り当てを証明書とすれば、SAT と 3SAT が NP に属することは直ちに分かる。各節を確かめるだけでよい。
SAT と 3SAT は NP完全である。
NP の言語 $L$ の入力 $w$ から、次の 3 段で論理式を作る。計算の表のマスの記号を定める(def-cl-row)。表の 1 行が次の行を局所的に決めることを示す(lem-cl-local)。表の正しさを節に書き、節を数える(def-cl-formula、prop-cl-count)。証明は節「主定理の証明」に置く。
以下、$L\in$ NP を固定し、定義の $\Sigma,\Sigma_1,\#,c,R$ と、$R$ を判定する機械 $M$ とその時間の上界 $|u|^d+d$ をとる。$\Gamma\setminus\{\sqcup\}$ は $\Sigma\cup\Sigma_1\cup\{\#\}$ を含むとする。入力 $w$、$n=|w|$ に対し
$$
N:=n^c+c,\qquad T:=(n+1+N)^d+d
$$
とおく。$T\ge n+1+N$ である。$|y|\le N$ なら $M$ は入力 $w\#y$ で $T$ ステップ以内に停止し、ヘッドはマス $-T,\dots,T$ の外に出ない。
様相は、状態をヘッドの下のマスに書き込めば 1 行で表せる。
マスの記号 の集合を $\mathcal{C}:=\Gamma\sqcup(Q\times\Gamma)$ とし、$s:=|\mathcal{C}|=|\Gamma|(1+|Q|)$ とおく。$(q,a)\in Q\times\Gamma$ を $[q,a]$ と書く。これは「ヘッドがここにあり、状態が $q$、記号が $a$」を表す。
様相 $C=(q,\tau,h)$ で $|h|\le T$ かつ $|i|>T$ のマスがすべて空白であるものの 行 を、$-T-1\le i\le T+1$ で
$$
\mathrm{row}(C)_i:=\begin{cases}[q,\tau(h)]&i=h\\ \tau(i)&i\ne h\end{cases}
$$
と定める。両端の $i=\pm(T+1)$ の値は $\sqcup$ である。
次の行の各マスは、上の行の 3 マスで決まる。
写像 $f\colon\mathcal{C}^3\to\mathcal{C}$ を、$(c_-,c_0,c_+)$ に対し上から順に最初に当てはまる行で定める。
| 条件 | $f(c_-,c_0,c_+)$ |
|---|---|
| $c_0=[q,a]$、$\delta(q,a)$ は未定義 | $[q,a]$ |
| $c_0=[q,a]$、$\delta(q,a)=(q',b,0)$ | $[q',b]$ |
| $c_0=[q,a]$、$\delta(q,a)=(q',b,\pm1)$ | $b$ |
| $c_0=a\in\Gamma$、$c_-=[q,e]$、$\delta(q,e)=(q',b,1)$ | $[q',a]$ |
| $c_0=a\in\Gamma$、$c_+=[q,e]$、$\delta(q,e)=(q',b,-1)$ | $[q',a]$ |
| $c_0=a\in\Gamma$、ほか | $a$ |
ヘッドの記号を 2 個含む組は、様相の行には現れない。そのような組の値も上の表で決めておく。
$C$ を $|h|< T$ の様相($|i|>T$ は空白)とし、$C'$ を次の様相($C$ が停止様相なら $C'=C$)とする。$\rho=\mathrm{row}(C)$、$\rho'=\mathrm{row}(C')$ とおくと、$|i|\le T$ で $\rho'_i=f(\rho_{i-1},\rho_i,\rho_{i+1})$ である。
要点:行にはヘッドの記号が 1 個だけあるので、変わるのはヘッドのマスと移動先だけである。
$C=(q,\tau,h)$ とする。$\delta(q,\tau(h))$ が未定義なら、表の 1 行目と最後の行から $\rho'=\rho$ である。$\delta(q,\tau(h))=(q',b,\epsilon)$ とする。$|h+\epsilon|\le T$ である。
$i=h$:$\epsilon=0$ なら $\rho'_h=[q',b]$、$\epsilon\ne0$ なら $\rho'_h=b$ で、表の 2・3 行目に一致する。
$i=h+1$、$\epsilon=1$:$\rho_i=\tau(i)\in\Gamma$、$\rho_{i-1}=[q,\tau(h)]$ で、4 行目から $[q',\tau(i)]=\rho'_i$ である。$i=h-1$、$\epsilon=-1$ も 5 行目から同じである。ここで $\rho_{i-1}$ はヘッドの記号でないので、4 行目は当てはまらない。
それ以外の $i$:$\rho_i=\tau(i)\in\Gamma$ である。$i=h+1$ で $\epsilon\ne1$ なら $\rho_{i-1}=[q,\tau(h)]$ だが移動の向きが違うので 4 行目に当たらず、5 行目にも当たらない。$i=h-1$ で $\epsilon\ne-1$ も同じである。$|i-h|\ge2$ なら両隣のマスに記号 $[\cdot,\cdot]$ がない。いずれも最後の行で $\tau(i)=\rho'_i$ である。$\square$
$0\le t\le T$、$-T-1\le i\le T+1$、$c\in\mathcal{C}$ ごとに、変数 $x_{t,i,c}$(時刻 $t$ のマス $i$ の記号が $c$)を用意する。$w\#$ の文字を $a_0,\dots,a_n$($a_n=\#$)とする。$\varphi_w$ を次の節の全体とする。
$\varphi_w$ の変数は $(T+1)(2T+3)s$ 個で、節はちょうど
$$
(T+1)(2T+3)\Bigl(1+\binom{s}{2}\Bigr)+2(T+1)+(2T+N)+T(2T+1)s^3+1
$$
個である。とくに $s$ を定数と見て節は $O(T^2)$ 個、変数も $O(T^2)$ 個である。節の幅は、(U)・(S) の長い節で $s$ 以下、(L) で $4$、(A) で $(2T+1)|\Gamma|$ である。
行は $T+1$ 本、列は $2T+3$ 本である。(U) は各マスに $1+\binom{s}{2}$ 個、(B) は各行に $2$ 個である。(S) は $|i|\le T$ の $2T+1$ マスのうち $n+1\le i\le n+N$ の $N$ マスを除く $2T+1-N$ 個の 1 リテラルの節と、$N$ 個の節と、$N-1$ 個の節で、合わせて $2T+N$ 個である($n+N\le T$ なので、この $N$ マスは範囲に入る)。(L) は $T(2T+1)$ 個の位置ごとに $s^3$ 個、(A) は $1$ 個である。$\square$
SAT が NP に属することは見た。任意の $L\in$ NP について $w\mapsto\varphi_w$ が $L$ から SAT への多項式時間還元であることを示す。
多項式時間で書き出せること. $L$ を固定すると $\mathcal{C}$ と $f$ は有限の表で、$T$ は $n$ の多項式である。prop-cl-count により節は $O(T^2)$ 個、リテラルは全体で $O(T^2)$ 個で、添字は $O(\log T)$ 桁である。よって $\varphi_w$ の長さは $n$ の多項式で抑えられ、添字についての入れ子の繰り返しで書き出せる。
$w\in L$ なら充足可能. $|y|\le N$、$w\#y\in R$ となる $y$ をとる。入力 $w\#y$ の計算を $C_0,C_1,\dots$ とし、停止した後は同じ様相をくり返すとする。$C_t$ のヘッドの位置の絶対値は $t$ 以下なので、$\mathrm{row}(C_t)$ が定義される。$x_{t,i,c}$ を $\mathrm{row}(C_t)_i=c$ のときに限り真とする。(U)・(B)・(S) は定義から成り立つ。(L) は、実際の $3$ マスの組では lem-cl-local により結論のリテラルが真で、ほかの組では否定のリテラルが真である。$M$ は $T$ ステップ以内に $q_{\mathrm{acc}}$ で停止するので、(A) も成り立つ。
充足可能なら $w\in L$. $\nu$ を $\varphi_w$ の充足する割り当てとする。(U) により、各 $(t,i)$ で真である $x_{t,i,c}$ はただ 1 つである。その $c$ を $\rho^t_i$ と書く。(S) により、マス $n+1$ から右は $\Sigma_1\cup\{\sqcup\}$ の記号で、いったん空白になるとマス $n+N$ まで空白であり、その先も空白である。よって最初の空白の手前までの語を $y\in\Sigma_1^*$ とすると $|y|\le N$ で、$\rho^0$ は入力 $w\#y$ の初期様相 $C_0$ の行である。
$t$ についての帰納法で $\rho^t=\mathrm{row}(C_t)$ を示す。$t=0$ は今見た。$t< T$ で成り立つとする。$C_t$ のヘッドの位置の絶対値は $t$ 以下で、$T$ より小さいので、lem-cl-local が使える。(L) の節を $(c_-,c_0,c_+)=(\rho^t_{i-1},\rho^t_i,\rho^t_{i+1})$ に当てはめると、否定のリテラルはすべて偽なので $x_{t+1,i,f(c_-,c_0,c_+)}$ が真である。(U) から $\rho^{t+1}_i=f(c_-,c_0,c_+)=\mathrm{row}(C_{t+1})_i$ である($|i|\le T$)。境界のマスは (B) から $\sqcup$ である。
(A) により $\rho^T$ のどこかのマスは $[q_{\mathrm{acc}},a]$ である。よって $C_T$ の状態は $q_{\mathrm{acc}}$ で、$M$ は $w\#y$ を受理する。すなわち $w\#y\in R$、$|y|\le N$ であり、$w\in L$ である。
以上で SAT は NP完全である。3SAT については次節の prop-cl-3sat と還元の推移性から従う。$\square$
CNF の論理式 $\varphi$ の、リテラルが $4$ 個以上の節 $\{\ell_1,\dots,\ell_k\}$ を、新しい変数 $z$ を使って $2$ つの節
$$
\{\ell_1,\ell_2,z\},\qquad\{\neg z,\ell_3,\dots,\ell_k\}
$$
に置き換える操作をくり返すと、どの節もリテラルが高々 $3$ 個の論理式 $\varphi'$ が得られる。$\varphi$ が充足可能であることと $\varphi'$ が充足可能であることは同値である。リテラルが $k\ge3$ 個の節 $1$ 本は $k-2$ 本の節と $k-3$ 個の新しい変数に変わる。とくに $\mathrm{SAT}\le_{\mathrm p}\mathrm{3SAT}$ である。
1 回の置き換えについて示せばよい。元の節 $D=\{\ell_1,\dots,\ell_k\}$ と、$D_1=\{\ell_1,\ell_2,z\}$、$D_2=\{\neg z,\ell_3,\dots,\ell_k\}$ を比べる。
割り当てが $D$ を充足するとする。$\ell_1,\ell_2$ のどちらかが真なら $z$ を偽とし、そうでなければ $\ell_j$($j\ge3$)が真なので $z$ を真とする。どちらも $D_1,D_2$ が真である。$z$ は新しい変数なので、ほかの節に影響しない。
逆に割り当てが $D_1,D_2$ を充足するとする。$z$ が真なら $D_2$ から $\ell_j$($j\ge3$)のどれかが真で、$z$ が偽なら $D_1$ から $\ell_1$ か $\ell_2$ が真である。どちらも $D$ が真である。
$D_2$ は $D$ より $1$ 個短いので、$k-3$ 回で幅が $3$ になる。節の総数は $k-3$ 増えて $k-2$ 本である。出力の長さは入力の長さの多項式で抑えられ、順に書き出せる。$\square$
prop-cl-count と合わせると、$\varphi_w$ は幅 $3$ で $O(T^2)$ 個の節の論理式に書き直せる。(L) の節 $1$ 本は $2$ 本になる。
$x$ と $\neg x$ を同時に含む節はいつも真なので除いてよい。節 $\{\ell_1,\ell_2\}$ は新しい変数 $z$ で $\{\ell_1,\ell_2,z\},\{\ell_1,\ell_2,\neg z\}$ に置き換えられ、節 $\{\ell\}$ も $2$ 回の同じ操作で $4$ 本にできる。したがって、どの節もちょうど $3$ 個の相異なる変数のリテラルからなる論理式に限っても、NP完全である。
証明は定理の主張より多くのことを与える(AB07 p. 50)。
$w$ の証明書 $y$($|y|\le N$、$w\#y\in R$)の全体と、$\varphi_w$ を充足する割り当ての全体の間に全単射があり、どちらの向きも多項式時間で計算できる。
主定理の証明の 2 つの向きが互いの逆を与える。$y$ から計算の表を作る写像と、割り当て $\nu$ の時刻 $0$ の行から $y$ を読む写像である。前者のあとに後者を行うと $y$ に戻る。逆の順については、充足する割り当ての表は帰納法の部分で $y$ の計算の表に等しいと示したので、$\nu$ に戻る。どちらも表の大きさの多項式時間で計算できる。$\square$
還元がこの性質をもつことを、証明書を移せる点に注目して Levin 還元、個数を保つ点に注目して 倹約的 という(AB07 p. 50)。prop-cl-3sat の還元はこのままでは個数を保たない。$\{\ell_1,\ell_2,\ell_3,\ell_4\}$ で $\ell_1,\ell_3$ が真なら、$z$ は真でも偽でもよい。
SAT が P に属するなら、充足する割り当てを多項式時間で求められる。したがって P $=$ NP なら、NP の任意の言語について、$w\in L$ の証明書を多項式時間で求められる。
要点:変数を $1$ つ真に固定した論理式の充足可能性を判定し、だめなら偽に固定する。
$\varphi$ が充足可能であるとする。変数 $x_1$ を真に固定した論理式 $\varphi|_{x_1}$($x_1$ を含む節を消し、$\neg x_1$ を節から除く)を判定する。充足可能なら $x_1$ を真に、そうでなければ $x_1$ を偽に固定した論理式は充足可能である。これを変数の個数だけくり返すと、充足する割り当てが得られる。空の節が現れた論理式は充足不可能として扱う。後半は prop-cl-parsimonious で割り当てから $y$ を読めばよい。P $=$ NP なら SAT は P に属する。$\square$
ここでの節数は $O(T^2)$ である。ヘッドの動きが入力によらない機械に $O(T\log T)$ 時間で模倣してから同様の符号化をすると、論理式の大きさは $O(T\log T)$ まで下がる(AB07 p. 50 の注意の 1。証明は同書の演習に任されており、この記事では証明しない)。
$\Sigma=\Sigma_1=\{0,1\}$ とし、$R$ を「$w\#y$ で $y$ が $1$ で始まる」語の言語とする。$M$ は $\#$ まで右へ進み、次のマスが $1$ なら受理状態へ移る。状態は走査、確認、受理、拒否の $4$ 個、$\Gamma=\{\sqcup,0,1,\#\}$ で $s=20$ である。$w=1$($n=1$)、$N=2$ とする。$M$ は入力 $u$ で $|u|+1$ ステップ以内に止まるので $T=5$ とできる。
prop-cl-count の節の個数は
$$
6\cdot13\cdot191+12+12+5\cdot11\cdot8000+1=454923
$$
で、変数は $1560$ 個である。実際に節を書き出して数えた値もこれに一致し、充足する割り当ては $3$ 個で、証明書 $1,10,11$ に対応する。節の大半は (L) の $440000$ 個である。この個数は $T$ について $2$ 次で増えるが、係数 $s^3$ は機械の大きさで決まる。
節 $\{a,b,c,d,e\}$ は、$\{a,b,z_1\}$、$\{\neg z_1,c,d,e\}$ を経て、$\{a,b,z_1\}$、$\{\neg z_1,c,z_2\}$、$\{\neg z_2,d,e\}$ になる。$5-2=3$ 本で、新しい変数は $5-3=2$ 個である。
幅 $3$ で NP完全になるが、幅 $2$ では易しい。
どの節もリテラルが高々 $2$ 個の論理式の充足可能性は、多項式時間で判定できる。
要点:変数に値を仮定して強制される値を伝播する。矛盾が出なければ、残りの節は元の節の部分集合である。
部分的な割り当て $\mu$ の 伝播 とは、$\mu$ でリテラルの $1$ つが偽で、もう $1$ つが未定の節があるとき、後者を真にする操作を、できなくなるまでくり返すことである。すべてのリテラルが偽の節が現れたら 矛盾 という。伝播は節の個数回で終わる。
手続き:未定の変数 $x$ を選び、$x$ を真と仮定して伝播する。矛盾すれば、$x$ を偽と仮定して伝播する。どちらも矛盾すれば拒否する。矛盾しなければ、その値を固定し、真のリテラルをもつ節を消して続ける。変数が尽きたら受理する。
矛盾せずに値を固定したとき、残った節はどれも未定の変数だけを含む。$1$ つのリテラルが偽の節は、幅が $2$ 以下なので、伝播で真になっているか、矛盾を起こしているからである。よって残りは元の節の部分集合で、残りを充足する割り当てと固定した値を合わせると、それまでの節も充足する。部分集合なので、元が充足可能なら残りも充足可能である。
どちらの仮定も矛盾するなら、その時点の節を充足する割り当ては、$x$ の値のどちらをとっても、伝播された値をとらざるをえず、矛盾する。よって充足不可能である。変数は高々その個数しか固定しないので、全体で多項式時間である。$\square$
同じ論法は幅 $3$ では働かない。$1$ つのリテラルが偽になっても、残りの $2$ 個のどちらが真か決まらず、値が強制されないからである。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| (U) の高々 1 つの節 | 下の機械 $M'$($L=\emptyset$) | $\varphi_w$ が充足可能 $\Rightarrow$ $w\in L$ |
| (A) の節 | $L=\emptyset$ の任意の機械 | 同上。$\varphi_w$ はいつも充足可能 |
| 証明書の長さの上界 | 停止問題 | $L\le_{\mathrm p}\mathrm{SAT}$ |
| 節の幅を $3$ から $2$ へ | 2SAT | P $\ne$ NP のもとで NP完全性 |
| 連言を選言に(DNF の充足可能性) | 各項を見るだけで判定できる | 同上 |
| 節を排他的論理和に | $\mathbb{F}_2$ 上の連立 $1$ 次方程式 | 同上 |
| 多対一の還元を Turing 還元に | 充足不可能性の問題 | 区別が失われる |
NP は、$1$ ステップごとに $2$ つの遷移関数のどちらかを選べる 非決定性 Turing 機械 が多項式時間で受理する言語の全体としても定義できる。これが元の定義である(AB07 p. 42)。証明書は選択の列にあたり、逆に証明書を最初に書き込む機械を作れば定義が移り合う。非決定性の機械に直接タブローを当てるときは、各時刻に選択を表す変数を $1$ つ足せばよい。
定理は AB07 Theorem 2.10(p. 45)である。AB07 は、ヘッドの動きが入力によらない $2$ テープの機械に直してスナップショットの列を符号化し、節の個数は定数倍の形で述べる(pp. 47–49)。この記事の符号化は $1$ 本テープの機械のマスの $3$ 個組による。幅を下げる分割は AB07 Lemma 2.15(p. 49)と同じ考え方である。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する