Cook–Levinの定理

同義語:Cook–Levin theoremCook-Levinの定理Cookの定理Cook's theorem

概要

Cook–Levinの定理(Cook–Levin theorem)とは、論理式の充足可能性の問題 SAT が NP完全である、という定理である。多項式時間の検証の計算全体を時刻とマスの表に書くと、表の正しさは隣り合う 3 マスの局所的な整合性の連言になり、$O(T^2)$ 個の節で表せる。分割によって各節のリテラルを 3 個以下にしても NP完全であり、一方 2 個以下なら多項式時間で判定できる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: Turing機械, 命題論理, 連言標準形

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$ を書いたものである。

P・NP・NP完全

受理状態 $q_{\mathrm{acc}}$($\delta(q_{\mathrm{acc}},\cdot)$ はどこでも定義されない)を指定した機械を考える。

  1. 言語 $R\subset\Delta^*$ が P に属するとは、機械 $M$ と $d\ge1$ があって、どの語 $u\in\Delta^*$ でも $M$ が $|u|^d+d$ ステップ以内に停止し、状態 $q_{\mathrm{acc}}$ で停止することと $u\in R$ が同値であることをいう。
  2. 言語 $L\subset\Sigma^*$ が NP に属するとは、アルファベット $\Sigma_1$、区切り記号 $\#\notin\Sigma\cup\Sigma_1$、$c\ge1$、P に属する言語 $R$ があって
    $$ w\in L\iff\text{ある }y\in\Sigma_1^*\text{ で }|y|\le|w|^c+c\text{ かつ }w\#y\in R $$
    が成り立つことをいう。$y$ を $w$ の 証明書 という。
  3. 写像 $f\colon\Sigma^*\to\Delta^*$ が機械で多項式時間で計算でき、$w\in A\iff f(w)\in B$ となるとき、$A\le_{\mathrm p}B$ と書く(多項式時間還元)。
  4. $B$ が NP完全 であるとは、$B$ が NP に属し、NP のすべての $A$ について $A\le_{\mathrm p}B$ となることをいう。

これは NP完全 の定義と同じである。還元の推移性や、NP完全な言語が P に属することと P $=$ NP の同値は、同記事の命題「還元の基本性質」で示されている。

SAT と 3SAT

変数 $x$ とその否定 $\neg x$ を リテラル という。リテラルの空でない有限集合を 節 といい、節の有限列を 連言標準形(CNF)の論理式という。真偽の割り当て $\nu$ が論理式を 充足する とは、どの節も $\nu$ で真になるリテラルを含むことをいう。充足する割り当てをもつ CNF の論理式(を符号化した語)全体を SAT、どの節もリテラルが高々 3 個である論理式に限ったものを 3SAT と書く。

変数の割り当てを証明書とすれば、SAT と 3SAT が NP に属することは直ちに分かる。各節を確かめるだけでよい。

Cook–Levin の定理

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})$ である。

行の 3 種類のマスを見る

要点:行にはヘッドの記号が 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$ を次の節の全体とする。

  • (U) 一意性. 各 $(t,i)$ について節 $\{x_{t,i,c}:c\in\mathcal{C}\}$ と、$c\ne c'$ の組ごとの節 $\{\neg x_{t,i,c},\neg x_{t,i,c'}\}$。
  • (B) 境界. 各 $t$ と $i=\pm(T+1)$ について節 $\{x_{t,i,\sqcup}\}$。
  • (S) 最初の行. 時刻 $0$ で、節 $\{x_{0,0,[q_0,a_0]}\}$、$1\le i\le n$ の節 $\{x_{0,i,a_i}\}$。$n+1\le i\le n+N$ の節 $\{x_{0,i,a}:a\in\Sigma_1\cup\{\sqcup\}\}$ と、$n+1\le i< n+N$ の節 $\{\neg x_{0,i,\sqcup},x_{0,i+1,\sqcup}\}$。$|i|\le T$ のほかのマスの節 $\{x_{0,i,\sqcup}\}$。
  • (L) 局所規則. $0\le t< T$、$|i|\le T$、$(c_-,c_0,c_+)\in\mathcal{C}^3$ ごとに節
    $$ \{\neg x_{t,i-1,c_-},\ \neg x_{t,i,c_0},\ \neg x_{t,i+1,c_+},\ x_{t+1,i,f(c_-,c_0,c_+)}\}. $$
  • (A) 受理. 節 $\{x_{T,i,[q_{\mathrm{acc}},a]}:|i|\le T,\ a\in\Gamma\}$。
節の個数

$\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$

3SAT への帰着

SAT から 3SAT への還元

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 回の分割を確かめる

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$ 本になる。

節の長さをちょうど 3 にする

$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$ 個である。

幅 2 との境目

幅 $3$ で NP完全になるが、幅 $2$ では易しい。

2SAT は P に属する

どの節もリテラルが高々 $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$ へ2SATP $\ne$ NP のもとで NP完全性
連言を選言に(DNF の充足可能性)各項を見るだけで判定できる同上
節を排他的論理和に$\mathbb{F}_2$ 上の連立 $1$ 次方程式同上
多対一の還元を Turing 還元に充足不可能性の問題区別が失われる
反例の確かめ
  • 高々 1 つの節. $M'$ は証明書の最初の記号 $e$ を読み、左へ戻って状態に $e$ を覚えたまま同じマスを読み直し、$e$ と異なる記号を読んだときに受理する機械とする。同じマスの記号は変わらないので、$M'$ はどの入力も受理せず、$L=\emptyset$ である。(U) の $\{\neg x_{t,i,c},\neg x_{t,i,c'}\}$ の形の節を除くと、時刻 $0$ のそのマスで $x_{0,i,0}$ と $x_{0,i,1}$ を両方真にでき、(L) が両方の場合の表を同時に真にして受理のマスまで届く。$w=1$、$N=1$、$T=6$ で節を実際に書き出して確かめると、除く前の論理式の充足する割り当ては $0$ 個で、除いた論理式は充足可能である。
  • 証明書の長さ. 長さの上界を外すと、停止する計算の全体の列を証明書にでき、停止問題が「NP に属する」形に書ける。しかし SAT は計算可能なので、$\mathrm{HALT}\le_{\mathrm p}\mathrm{SAT}$ なら停止問題も計算可能になり、矛盾する(計算可能性理論)。タブローの大きさは計算の長さで決まるので、上界がなければ有限の表に収まらない。
  • 幅 $2$. prop-cl-2sat による。P $\ne$ NP なら NP完全でない(NP完全なら P $=$ NP になる)。
  • DNF. 項(リテラルの連言)の 1 つが $x$ と $\neg x$ を同時に含まなければ充足可能である。CNF を DNF に展開すると長さが指数的になりうるので、SAT の還元にはならない。
  • 排他的論理和. 各節が「リテラルの和が $1$」なら、Gauss の消去法で判定できる。
  • Turing 還元. 論理式の充足不可能性は、SAT の判定を $1$ 回呼んで答えを反転すれば判定できる。Cook の元の定義の還元はこの形である(AB07 p. 63 の演習 12)。一方、充足不可能性の言語が多対一の還元で SAT に帰着するなら、それは NP に属し NP $=$ coNP となる。これは未解決である(AB07 p. 57)。

非決定性 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)と同じ考え方である。

関連項目

参考文献

[1]
[2]
Sanjeev Arora; Boaz Barak, Computational Complexity: A Modern Approach, Web draft(2007-01-08)。刊行版は 2009 年, Cambridge University Press, 2009, 頁は Web draft 2007-01-08 の通し頁:§2.1.2(非決定性 Turing 機械)p. 42、§2.3 p. 44、Theorem 2.10 p. 45、Lemma 2.12 の証明 pp. 47–49、Lemma 2.15 p. 49、§2.3.6 p. 50、§2.6.1 p. 57、章末の注 p. 61、Exercise 12 p. 63

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する