Cook-Levinの定理
Cook-Levin theorem
定理
Proof.
$ L \in \mathbf{NP}をとる
$ x \in L \iff \exists_{u \in 2^{p(|x|)}}[ M_{T(|x|)}(x, u) = 1]
$ Mをシミュレートする計算時間$ J(n) = O(T(n)^2)の2-tape oblivious TM$ M^\mathsf{oblv} = (Q, \Gamma, \delta)をとる 各$ nについて$ \forall_{x \in 2^n} \lbrack x \in L \iff \Psi_x \in \mathrm{SAT} \rbrackを満たすCNF$ \Psi_x\colon 2^{O(J(n))} \to 2 が存在する $ \Phi_\mathsf{tr} \colon (z_1, b, z_0, z_{-1}) \mapsto z_1 =^{?} F_M^n(b, z_0, z_{-1}) \colon 2^{O(\|Q\|+\|\Gamma\|)} \to 2
$ \Phi_\mathsf{start}\colon z \mapsto z =^? z_\mathsf{start} \colon 2^{O(\|Q\|+\|\Gamma\|)} \to 2
$ \Phi_\mathsf{halt}\colon z \mapsto z =^? z_\mathsf{halt} \colon 2^{O(\|Q\|+\|\Gamma\|)} \to 2
は高々サイズ$ O(l2^{l})のCNFで表現できる。$ lは$ xや$ |x|に依存しないので$ O(1) $ \Phi_{\mathsf{initial}(x)} \colon y \mapsto x \preceq^? y \colon 2^{O(n + p(n))} \to 2を表現するCNFは次のように定義すると大きさは$ O(n) $ \Phi_{\mathsf{initial}(x)}(y) \coloneqq \bigwedge_{i < n} t_{x_i}(y_i) $ t_0(y_i) := \neg y_i $ t_1(y_i) = y_i
以下のように$ \Psi_xを定義する
$ \Psi_x(y, z_1, ..., z_{J(n)} ) \coloneqq \Phi_{\mathsf{initial}(x)}(y) \land \Phi_\mathsf{start}(z_0) \land \Phi_\mathsf{halt}(z_{J(n)}) \land \bigwedge_{s < J(n)} \Phi_\mathsf{tr}(z_{s+1}, y^{h_0^s[n]}, z_s, z_{\tau^s[n]})
上の結果より
$ |\Psi_x| = O(n+J(n))
よって
$ x \in L \iff \exists_{u \in 2^{p(|x|)}}[ M^\mathsf{oblv}_{J(|x|)}(x, u) = 1]
$ \iff \exists_{u \in 2^{p(|x|)}} \left[z_\mathsf{start} \to^{T(|x|)}_{M, x^\frown u} z_\mathsf{halt(1)}\right]
$ \iff \exists u,z_1, ..., z_{J(|x|)} \left[z_0 = z_\mathsf{start} \land z_{J(|x|)} = z_\mathsf{halt(1)} \land z_0 \to_{M,x^\frown u} z_1 \to_{M,x^\frown u} ... \to_{M,x^\frown u} z_{J(|x|)} \right]
$ \iff \exists u, z_1, ..., z_{J(n)}. \left[\Phi_\mathsf{start}(z_0) \land \Phi_\mathsf{halt}(z_{J(n)}) \land \bigwedge_{s < J(n)} \Phi_\mathsf{tr}(z_{s+1}, (x^\frown u)^{h_0^s[n]}, z_s, z_{\tau^s[n]}) \right]
$ \iff \exists y, z_1, ..., z_{J(n)} \left[ \Phi_{\mathsf{initial}(x)}(y) \land \Phi_\mathsf{start}(z_0) \land \Phi_\mathsf{halt}(z_{J(n)}) \land \bigwedge_{s < J(n)} \Phi_\mathsf{tr}(z_{s+1}, y^{h_0^s[n]}, z_s, z_{\tau^s[n]}) \right]
$ x \in L \iff \Psi_x \in \mathrm{SAT}
右辺の論理式$ \Psi_xの大きさは$ |\Psi_x| = O(n+J(n))
$ \text{SAT} \le_p \text{3SAT}
任意の$ k \ge 3, $ \Phi_{k+1} \in (k+1)\mathrm{SAT}について$ \Phi_{k+1} \in (k+1)\mathrm{SAT} \iff \Phi_k \in k\mathrm{SAT}を満たす$ \Phi_kが存在する
$ \Phi_{k+1}の各節について以下の変換を行う $ zは新しい変項
$ b_0 \lor...\lor b_{k} \lor b_{k+1} \mapsto (b_0 \lor...\lor z) \land (\neg z \lor b_k \lor b_{k+1})
このとき$ b_0 \lor...\lor b_{k} \lor b_{k+1} \in (k+1)\mathrm{SAT} \iff (b_0 \lor...\lor z) \land (\neg z \lor b_k \lor b_{k+1}) \in k\mathrm{SAT}
この変換は多項式時間計算可能なので$ \mathrm{SAT} \le_p \mathrm{3SAT} ❏ 定理