NP完全

1．$t$ ステップで書き換えられるのはマス $-t,\dots,t$ だけで、残りのマスには入力が残ることから従う。

1．還元の写像 $f,g$ について $g\circ f$ は lem-np-composition の 2 により多項式時間で計算でき、$w\in A\iff f(w)\in B\iff g(f(w))\in C$ である。
2．還元の写像を $f$ とすると $A=f^{-1}(B)$ であり、lem-np-composition の 2 から従う。
3．NP の任意の言語 $A$ について $A\le_{\mathrm p}B$ なので、1 により $A\le_{\mathrm p}C$ である。
4．$B$ が P に属するなら、NP の任意の $A$ は $A\le_{\mathrm p}B$ なので 2 により P に属する。P はつねに NP に含まれるので P $=$ NP である。逆に P $=$ NP なら、NP に属する $B$ は P に属する。$\square$

SAT が NP に属することは上で見た。NP に属する任意の言語 $L\subset\Sigma^*$ について $L\le_{\mathrm p}\mathrm{SAT}$ を示す。NP の定義の $\Sigma_1,\#,c,R$ をとり、$R$ を多項式時間で判定する機械 $M=(Q,\Gamma,\sqcup,q_0,\delta)$ と、その時間の上界 $|u|^{d}+d$（$d\ge1$）をとる。$p(s)=s^{d}+d$ とおくと $p$ は単調増加で $p(s)\ge s$ である。
入力 $w\in\Sigma^*$、$n=|w|$ に対し、$N=n^{c}+c$、$T=p(n+1+N)$ とおく。証明書 $y$ は $|y|\le N$ なので $|w\#y|\le n+1+N$ であり、$M$ は入力 $w\#y$ で $T$ ステップ以内に停止する。$T$ ステップの間、ヘッドはマス $-T,\dots,T$ の外に出ない。$M$ の計算を $T+1$ 行 $2T+1$ 列の表に書き、停止した後は同じ様相をくり返すとみなす。この表を変数で表す。$0\le t\le T$、$-T\le i\le T$、$a\in\Gamma$、$q\in Q$ について、次の命題変数を用意する。

• $X_{t,i,a}$：時刻 $t$ にマス $i$ の記号が $a$ である。
• $H_{t,i}$：時刻 $t$ にヘッドがマス $i$ にある。
• $S_{t,q}$：時刻 $t$ に状態が $q$ である。
  論理式 $\varphi_w$ を次の節の全体とする（$\to$ を含む式は、それと同値な節に書き直したものを表す。たとえば $\alpha\wedge\beta\wedge\gamma\to\eta$ は節 $\{\neg\alpha,\neg\beta,\neg\gamma,\eta\}$ である）。

1. ただ 1 つ．各 $(t,i)$ について節 $\{X_{t,i,a}:a\in\Gamma\}$ と、$a\ne b$ ごとの節 $\{\neg X_{t,i,a},\neg X_{t,i,b}\}$。各 $t$ について、$H_{t,i}$（$i$ を動かす）と $S_{t,q}$（$q$ を動かす）にも同じ形の節。
2. 初期の行．$S_{0,q_0}$、$H_{0,0}$、$0\le i< n$ で $X_{0,i,w_{i+1}}$、$X_{0,n,\#}$ の 1 リテラルの節。$n+1\le i\le n+N$ で節 $\{X_{0,i,a}: a\in\Sigma_1\cup\{\sqcup\}\}$ と、$n+1\le i< n+N$ で $X_{0,i,\sqcup}\to X_{0,i+1,\sqcup}$。そのほかの $i$ で $X_{0,i,\sqcup}$。
3. 遷移．$t< T$、$i$、$q$、$a$ ごとに、$\delta(q,a)=(q',b,D)$ が定義され、$D$ に応じた移動量を $\epsilon\in\{-1,0,1\}$ とするとき、$|i+\epsilon|\le T$ なら
   $$ S_{t,q}\wedge H_{t,i}\wedge X_{t,i,a}\to S_{t+1,q'},\quad \cdots\to X_{t+1,i,b},\quad \cdots\to H_{t+1,i+\epsilon} $$
   の 3 つの節（$\cdots$ は同じ前提）、$|i+\epsilon|>T$ なら節 $\{\neg S_{t,q},\neg H_{t,i},\neg X_{t,i,a}\}$。$\delta(q,a)$ が定義されていなければ、同じ前提から $S_{t+1,q}$、$X_{t+1,i,a}$、$H_{t+1,i}$ を導く 3 つの節。
4. ヘッドのないマス．$t< T$、$i$、$a$ ごとに $\neg H_{t,i}\wedge X_{t,i,a}\to X_{t+1,i,a}$。
5. 受理．$S_{T,q_{\mathrm{acc}}}$ の 1 リテラルの節。

大きさ．$\varphi_w$ の変数と節の個数は $T$ の多項式で、$w$ から多項式時間で書き出せる。

論理式 $\varphi$ の各節 $C=\{\ell_1,\dots,\ell_k\}$ を次のように置き換えた論理式を $\varphi'$ とする。$k\le3$ ならそのまま残す。$k\ge4$ なら、節ごとに新しい変数 $z_1,\dots,z_{k-3}$ を用意して、$k-2$ 個の節
$$ \{\ell_1,\ell_2,z_1\},\ \{\neg z_1,\ell_3,z_2\},\ \dots,\ \{\neg z_{k-4},\ell_{k-2},z_{k-3}\},\ \{\neg z_{k-3},\ell_{k-1},\ell_k\} $$
に置き換える（$2\le i\le k-3$ の節は $\{\neg z_{i-1},\ell_{i+1},z_i\}$）。$\varphi'$ は多項式時間で書き出せる。

3SAT の論理式 $\varphi=(C_1,\dots,C_r)$ から、グラフ $G_\varphi$ を次のように作る。頂点は、各節 $C_j$ と $C_j$ のリテラル $\ell$ の組 $(j,\ell)$ である。同じ節の 2 頂点 $(j,\ell),(j,\ell')$ を結び、互いに否定の関係にあるリテラルの頂点 $(j,\ell)$ と $(j',\neg\ell)$ を結ぶ。$w(\varphi)=(G_\varphi,r)$ とおく。頂点は高々 $3r$ 個で、多項式時間で書き出せる。
充足する割り当てから各節の真のリテラルを 1 つずつ選べば大きさ $r$ の独立集合になり、逆に大きさ $r$ の独立集合は各節からちょうど 1 頂点を選び、矛盾のない割り当てを定める。

部品．入力の頂点 $u,v$ に対し、新しい頂点 $p,q,o$ を三角形に結び、辺 $up$、$vq$ を加えたものを論理和の部品といい、$o$ をその出力とする。色を $\mathsf T,\mathsf F,\mathsf N$ とし、$u,v$ の色が $\{\mathsf T,\mathsf F\}$ に属するとき次が成り立つ。

• (i) $u,v$ がともに $\mathsf F$ なら、どの 3 彩色でも $o$ は $\mathsf F$ である。$p\ne\mathsf F$、$q\ne\mathsf F$ で $p\ne q$ なので $\{p,q\}=\{\mathsf T,\mathsf N\}$ となり、三角形の残りの $o$ は $\mathsf F$ である。
• (ii) $u,v$ の少なくとも一方が $\mathsf T$ なら、$o$ を $\mathsf T$ にする部品の彩色がある。$u=v=\mathsf T$ なら $p=\mathsf F$、$q=\mathsf N$。$u=\mathsf T$、$v=\mathsf F$ なら $p=\mathsf F$、$q=\mathsf N$。$u=\mathsf F$、$v=\mathsf T$ なら $p=\mathsf N$、$q=\mathsf F$。いずれも $o=\mathsf T$ で、部品の辺の両端は異なる色である。

構成．3SAT の論理式 $\varphi$ からグラフ $G_\varphi$ を作る。三角形をなす 3 頂点 $\mathsf T,\mathsf F,\mathsf N$（色と同じ名前で呼ぶ）を置く。各変数 $x$ に頂点 $x$ と $\bar x$ を置き、$x$、$\bar x$、$\mathsf N$ を三角形に結ぶ。リテラル $\neg x$ の頂点は $\bar x$ とする。各節は、リテラルを重複させて 3 個に並べ $(\ell_1,\ell_2,\ell_3)$ とし（1 個なら $(\ell_1,\ell_1,\ell_1)$、2 個なら $(\ell_1,\ell_2,\ell_2)$）、入力 $\ell_1,\ell_2$ の論理和の部品の出力 $o_1$ と、入力 $o_1,\ell_3$ の部品の出力 $o_2$ を作り、$o_2$ を頂点 $\mathsf F$ と $\mathsf N$ に結ぶ。頂点は $3+2(\text{変数の数})+6(\text{節の数})$ 個で、多項式時間で書き出せる。
彩色から割り当てへ．$G_\varphi$ の 3 彩色をとる。頂点 $\mathsf T,\mathsf F,\mathsf N$ は三角形なので相異なる色をもち、色の名前を付け替えて、それぞれ色 $\mathsf T,\mathsf F,\mathsf N$ をもつとしてよい。変数の頂点 $x,\bar x$ は $\mathsf N$ と隣接し互いに隣接するので、一方が $\mathsf T$、他方が $\mathsf F$ である。$x$ の色が $\mathsf T$ のとき $x$ を真とすると、各リテラルの頂点の色が $\mathsf T$ であることとリテラルが真であることが同値になる。ある節のリテラルがすべて偽なら、(i) により $o_1=\mathsf F$、もう一度 (i) により $o_2=\mathsf F$ だが、$o_2$ は頂点 $\mathsf F$ と隣接するので矛盾する。よって割り当ては $\varphi$ を充足する。
割り当てから彩色へ．真のリテラルの頂点に $\mathsf T$、偽のものに $\mathsf F$ を付け、各節の部品を (i)(ii) で塗れば、$o_2=\mathsf T$ となる 3 彩色が得られる。

$k$ についての帰納法で示す。グラフ $G$ に、すべての頂点と隣接する新しい頂点 $a$ を加えたグラフを $G^+$ とする。$G$ が $k$ 色で塗れるなら、$a$ に新しい色を付けて $G^+$ は $k+1$ 色で塗れる。$G^+$ が $k+1$ 色で塗れるなら、$a$ の色は $G$ のどの頂点にも使われないので、$G$ は残りの $k$ 色で塗れる。$G\mapsto G^+$ は多項式時間で計算できるので $k\mathrm{COL}\le_{\mathrm p}(k+1)\mathrm{COL}$ であり、prop-np-reduction の 3 から従う。$\square$

次の手続きを考える。各連結成分で頂点 $r$ を 1 つ選び、幅優先探索で $r$ からの距離 $d(v)$ を求め、$d(v)$ の偶奇で色を付ける。最後に、すべての辺の両端の色が異なるかを確かめ、異なれば受理する。手間は頂点数と辺数の多項式である。
受理したなら 2 彩色が得られており、拒否したなら長さが奇数の閉じた歩道があるので 2 彩色は存在しない。