充足可能性問題が NP 完全であることの証明

Turing 機械についての理解を前提とする．またここでは，Turing 機械のテイプはスタートゥ位置を左の終端とし，それ以上左に動くことはできないものとする．

Definition 1. 決定問題

$A$ を無限集合とする．写像 $P: A \to \{0, 1\}$ を決定問題と云ふ．

Definition 2. $\mathrm{NP}$

決定問題 $P: A \to \{0, 1\}$ がクラス $\mathrm{NP}$ に属する，或いは単に $\mathrm{NP}$ であるとは，ある非決定性 Turing 機械 $M$ が存在して，次の2条件を満たすことを云ふ．

• ある多項式 $p$ が存在し，任意の入力 $x \in A$ に対しても，$M(x)$ は $p(|x|)$ ステプで停止する．
• 任意の入力 $x \in A$ に対し，$M(x) = P(x)$ である．ここで，$M(x)$ は $M$ が $x$ を受理するなら $M(x) =1$ であり，さもなくば $M(x) = 0$ である．

よくアルガリズァムの教科書で述べられてゐるやうな $\mathrm{NP}$ の定義は以下であらう．実際，これは上の定義と一致する．

Theorem 3. $\mathrm{NP}$ の別定義

決定問題 $P: A \to \{0,1\}$ が $\mathrm{NP}$ であることと，ある決定性 Turing 機械 $M$ と多項式 $p, q$ が存在して，次の3条件を満たすことは同値．

• 任意の $x \in A$ と文字列 $y$（これを証拠と云ふ）に対しても，$M(x, y)$ は $p(|x|)$ ステプで停止する．
• $P(x) = 1$ であるならば，ある長さ $q(|x|)$ の文字列 $y$ が存在して，$M(x, y) = 1$ となる．
• $P(x) = 0$ であるならば，どんな証拠 $y$ に対しても $M(x, y) = 0$ である．

proof. ($\Longrightarrow$) $N$ を $P$ を解くやうな非決定性 Turing 機械とする．勝手に $x \in A$ をとる．このとき，$\mathrm{NP}$ の定義からある多項式 $p$ が存在し，$N$ は $p(|x|)$ ステプで停止する．そこで，$N$ が停止するまでの $N$ の状態遷移の列を考へ，それを $(s_0,\dots,s_{p(|x|)})$ とする．決定性 Turing 機械 $M=M(x, y)$ として，$x$ を入力された $N$ が，任意の $i = 1,\dots, p(|x|)$ に対してステプ $i$ で状態 $s_{i-1}$ から $s_{i}$ に遷移できるか確認し，かつ最終的に $N$ が受理状態に達するなら $1$ を出力し，さもなくば $0$ を出力すると云ふものを考へる．この $M$ は上で定義した別定義の上2つの条件は満たしてゐる．またもし $N$ が $x$ を受理しないなら，受理状態に達するような$N$の妥当な状態列は存在しないから $M$ は常に $0$ を出力するので，3つ目の条件も満たしてゐる．

($\Longleftarrow$) 非決定性 Turing 機械 $N = N(x)$ として，上の定義の2番目を満たすやうな長さ $q(|x|)$ の文字列 $y$ が存在するならば $1$ を出力し，さもなくば $0$ を出力するやうなものを考へる．$N$ が非決定性であることから，任意の $x \in A$ に対してこれは $p(|x|)$ ステプで停止する（全ての長さ $q(|x|)$ の文字列 $y$ に対して $M(x, y)$ を並列して動作させれば良い）．もし $P(x) = 1$ であるならば，$N$ は $1$ を出力し，さもなくば $N$ は $0$ を出力する．∎

Definition 4. 多項式還元

写像 $P: A \to \{0, 1\}, Q: B \to \{0, 1\}$ を何れも決定問題とする．$P$ が $Q$ に多項式還元可能であるとは，ある Turing 機械 $M$ と多項式 $p$ が存在して，任意の $a \in A$ に対して，$M(a)$ は $p(|a|)$ ステプである値 $b \in B$ を出力し，かつ $Q(b) = P(a)$ となることを云ふ．

Definition 5. $\mathrm{NP}$ 完全

あるクラス $\mathrm{NP}$ に属する決定問題 $P$ が $\mathrm{NP}$ 完全であるとは，クラス $\mathrm{NP}$ に属する任意の決定問題 $Q$ が $P$ に多項式還元可能であることを云ふ．

Definition 6. 充足可能性問題 (Satisfiability; SAT)

論理変数 $x_1, \dots, x_n$ を変数とするやうな論理式 $f=f(x_1,\dots,x_n)$ が与へられたときに， $f(a_1, \dots, a_n) = 1$ となるやうな変数割当 $x_1 = a_1, \dots, x_n = a_n$ が存在するかどうかを判定する決定問題を充足可能性問題と云ふ．このやうな変数割当てが存在するとき，充足可能性問題は解を持つと云ふ．

Definition 7. 節 連言標準形

1個以上の論理変数を論理和で結んだものを節と云ふ．論理式 $f$ が節を論理積で結んだ形式で書かれてゐるとき，$f$ は連言標準形であると云ふ．

Theorem 8. Cook-Levin の定理

充足可能性問題は $\mathrm{NP}$ 完全である．

proof. 充足可能性問題が $\mathrm{NP}$ に属することは，全ての変数割当てを並列で試せば良いことから明らかである．勝手にクラス $\mathrm{NP}$ に属する決定問題 $P: A \to \{0, 1\}$ と，$P$ を解くやうな非決定性 Turing 機械 $M$ を取る．

ここで，$M$ の状態 $S$ を $S=\{s_0, \dots, s_{X-1} = s_A\}$，記号 $\Gamma$ を $\Gamma = \{a_0 = \sqcup, a_1, \dots, a_{Y-1}\}$ とする．ただし $s_0$ を初期状態とし，$s_A$ は受理状態で，$\sqcup$ は空記号である．また，状態遷移関数を $\delta(s_i, a_j) = (s_{\sigma(i)}, a_{\tau(j)}, d)$ で表す．論理変数 $A_{i, j}, B_{i, j}, C_{i, j, k}$ を次のやうに定義する．

• $A_{i, j}$: $M(x)$ の動作のステプ $i$ において，$M$ が状態 $s_j$ であるならば True，さもなくば False となる変数．
• $B_{i, j}$: $M(x)$ の動作のステプ $i$ において，$M$ のヘドゥがテイプ位置 $j$ にある場合 True，さもなくば False となる変数．
• $C_{i, j, k}$: $M(x)$ の動作のステプ $i$ において，テイプ位置 $j$ に記号 $s_k$ が書かれてゐるならば True，さもなくば False となる変数．

ここで，ある多項式 $p$ が存在し，$M$ は $p(|x|)$ ステプで終了することから，使用するテイプ領域も高々 $p(|x|)$ 個であり，全ての変数の数は高々多項式オーダで抑へられることに気をつける．表記を簡潔にするため，以降 $p(|x|) = n$ とおく．

• $i = 0, \dots, n$ に対して，節 $\alpha_i$ を $\alpha_i = A_{i, 0} \lor \dots \lor A_{i, X-1}$ で定義する．これは $M$ がどのステプ $i$ でも何れかの状態にあることを意味する．
• $i = 0, \dots, n$ と $0 \leq j < j' \leq X-1$ に対して，節 $\beta_{i, j}$ を $\beta_{i, j} = \lnot A_{i, j} \lor \lnot A_{i, j'}$ で定義する．これは，$M$ がどのステプ $i$ でもただ1つの状態であること（2つ以上の状態を取らないこと）を意味する．
• $i=0,\dots,n$ に対して，節 $\gamma_i$ を $\gamma_i = B_{i, 0} \lor \dots \lor B_{i, i}$ で定義する．これはステプ $i$ に $M$ のヘドゥがゐるテイプ位置は $0, \dots, i$ の何れかであることを意味する．
• $i = 0, \dots ,n$ と $0 \leq j < j' \leq i$ に対して，節 $\delta_{i, j}$ を $\delta_{i, j} = \lnot B_{i, j} \lor \lnot B_{i, j'}$ で定義する．これは，どのステプ $i$ でも $M$ のヘドゥの位置はただ1つであることを意味する．
• $i = 0, \dots, n$と$j = 0, \dots, n$ に対して，節 $\varepsilon_{i, j}$ を $\varepsilon_{i, j} = C_{i,j,0} \lor \dots \lor C_{i, j, Y-1}$ で定義する．これは，どのステプ $i$ でもテイプ位置 $j$ には何れかの記号が書かれてゐることを意味する．
• $i = 0, \dots, n$, $j = 0, \dots, n$, $0 \leq k < k' \leq n$ に対して，節 $\zeta_{i, j, k}$ を $\zeta_{i, j, k} = \lnot C_{i,j,k} \lor \lnot C_{i, j, k'}$ で定義する．これは，どのステプ $i$ でもテイプ位置 $j$ に書かれてゐる記号はただ1つであることを意味する．
• $i=0,\dots, n$, $j=0,\dots,n$, $k = 0, \dots, Y-1$ に対して節 $\eta_{i,j,k}$ を $\eta_{i,j,k} = B_{i,j} \lor \lnot C_{i,j,k} \lor C_{i+1, j, k}$ で定義する．これは，ステプ $i$ でヘドゥがテイプ位置 $j$ にないのならば，テイプ位置 $j$ に書かれてゐる記号はステプ $i$ と $i+1$ で変化しないと云ふことを意味する．
• $i=0,\dots, n$, $j=0,\dots,X-1$, $k = 0, \dots, n$, $l = 0, \dots, Y-1$ に対して節 $\theta_{i, j, k, l}$ を $\theta_{i,j,k,l} = \lnot A_{i, j} \lor \lnot B_{i, k} \lor \lnot C_{i,k,l} \lor A_{i+1, \sigma(i)}$ で定義する．これは，ステプ $i$ で状態が $s_j$ であり，テイプ位置が $k$ で $k$ に $a_l$ と云ふ記号が書かれてゐるのならば，状態遷移関数によりステプ $i+1$ の状態は $s_\sigma(i)$ に遷移すると云ふことを表してゐる．
• $i=0,\dots, n$, $j=0,\dots,X-1$, $k = 0, \dots, n$, $l = 0, \dots, Y-1$ に対して節 $\iota_{i, j, k, l}$ を $\iota_{i,j,k,l} = \lnot A_{i, j} \lor \lnot B_{i, k} \lor \lnot C_{i,k,l} \lor B_{i+1, k+d}$ で定義する．これは，ステプ $i$ で状態が $s_j$ であり，テイプ位置が $k$ で $k$ に $a_l$ と云ふ記号が書かれてゐるのならば，状態遷移関数によりステプ $i+1$ のヘドゥの位置は $k+d$ に遷移すると云ふことを表してゐる．
• $i=0,\dots, n$, $j=0,\dots,X-1$, $k = 0, \dots, n$, $l = 0, \dots, Y-1$ に対して節 $\kappa_{i, j, k, l}$ を $\kappa_{i,j,k,l} = \lnot A_{i, j} \lor \lnot B_{i, k} \lor \lnot C_{i,k,l} \lor C_{i+1, k, \tau(l)}$ で定義する．これは，ステプ $i$ で状態が $s_j$ であり，テイプ位置が $k$ で $k$ に $a_l$ と云ふ記号が書かれてゐるのならば，状態遷移関数によりステプ $i+1$ でテイプ位置 $k$ に書かれてゐる記号は $a_\tau(l)$ であると云ふことを表してゐる．

これらの節らと，次の初期状態，受理状態に関はる節を論理積で結んだ論理式 $f$ を考へる．

• ステプ $0$ で $M$ の状態は $s_0$ なので，$A_{0, 0}$．
• ステプ $0$ で $M$ のヘドゥの位置は $0$ なので，$B_{0, 0}$．
• テイプに初め入力が書かれてゐるはずなので，$i=0,\dots,|x|$ に対して，$C_{0, i, \lambda(x_i)}$．ただし $x_i$ は $x$ の $i$ 文字目を表し，$\lambda: \Lambda \to \mathbb{N}$ は記号 $x \in \Lambda$ に対して $x=s_k$ となるやうな $k$ を返す写像である．また，それ以外のテイプに書かれてゐるのは空白記号なので，$i=|x|+1,\dots,p(|x|)$ に対して，$C_{0, i, 0}$．
• ステプ $p(|x|)$ で受理状態に到達するので，$A_{p(|x|), X-1}$．

このやうにして作られた $f$ は充足可能性問題として解くことができる．もし，$P(x)=1$ であるならば，$M$ は $x$ を受理するので，受理状態まで達する状態列が存在すると云ふことだから，当然充足可能性問題も解を持つ．また，$P(x)=0$ であるならば，受理状態まで達する状態列は存在しないので，この充足可能性問題が解を持つことはない．$f$ への変形は多項式ステプで可能だから，これは任意のクラス $\mathrm{NP}$ に属する決定問題が充足可能性問題に多項式還元できると云ふことであり，充足可能性問題が $\mathrm{NP}$ 完全であることが云へた．∎