NP 完全性と Cook–Levin の定理 | 計算理論

1 Boolean 論理式と SAT

変数記号を $z_1,z_2,\ldots$ とする。式は有限文字列として符号化し、変数の添字と括弧を含む符号長を式の長さとする。

定義 1.1. Boolean 論理式 (Boolean formula) は、変数 $z_i$ 、定数 $0,1$ 、否定 $\neg$ 、論理和 $\lor$ 、論理積 $\land$ から有限回の構成で得られる式である。式に現れる変数への割当 (truth assignment) は、各変数へ $0$ または $1$ を対応させる写像であり、演算

\neg 0=1,\quad \neg1=0,\quad a\lor b=\max\{a,b\},\quad a\land b=\min\{a,b\}

によって式の値を定める。値が $1$ となる割当が存在する式を充足可能 (satisfiable) という。

変数または変数の否定をリテラル (literal) という。リテラルの有限個の論理和を節 (clause) といい、節の有限個の論理積である式を連言標準形 (conjunctive normal form)（CNF）という。

正しく符号化された充足可能な Boolean 論理式全体の言語を

\mathsf{SAT}

とする。不正な式の符号は $\mathsf{SAT}$ に含めない。

CNF の節に含めるリテラル数には上限を置かない。特に、本記事は各節を高々三リテラルに制限する 3SAT を扱わない。

命題 1.2.

\mathsf{SAT}\in\mathsf{NP}

である。

証明. 入力 $\varphi$ が正しい Boolean 論理式の符号でなければ拒否する。正しい式なら、 $\varphi$ に現れる相異なる変数を出現順に列挙する。証明書を各変数の値を表すビット列とし、列挙した変数数と同じ長さであることを確認する。

検証器は構文木の葉から根へ値を計算する。各変数葉には証明書の対応するビットを置き、各否定・論理和・論理積の頂点では子の値から一回の Boolean 演算で値を得る。変数名を表へ登録して参照する処理を単純な逐次探索で実装しても、式の符号長を $m$ とすれば $O(m^2)$ 時間で終わる。証明書長は式に現れる変数数以下であり、高々 $m$ である。

$\varphi$ が充足可能なら、その充足割当を証明書にすれば検証器は受理する。検証器が受理したなら、証明書が定める割当の下で構文木の根の値が $1$ であるため、 $\varphi$ は充足可能である。§E15.11 定理 3.1により $\mathsf{SAT}\in\mathsf{NP}$ である。▨

2 NP 困難性と NP 完全性

定義 2.1. 言語 $B$ がNP 困難 (NP-hard) であるとは、任意の言語 $A\in\mathsf{NP}$ について

A\le_{\mathrm p}B

が成り立つことをいう。 $B$ が NP 困難かつ $B\in\mathsf{NP}$ であるとき、 $B$ をNP 完全 (NP-complete) という。

NP 困難性だけでは、対象言語自身が NP に属することを要求しない。NP 完全性では、NP への所属と NP の全言語からの帰着を別々に確認する。

命題 2.2. $B$ が NP 完全で $B\in\mathsf P$ ならば、

\mathsf P=\mathsf{NP}

である。

証明.§E15.11 命題 1.4により $\mathsf P\subseteq\mathsf{NP}$ である。任意の $A\in\mathsf{NP}$ をとる。 $B$ の NP 困難性から $A\le_{\mathrm p}B$ であり、 $B\in\mathsf P$ と§E15.11 命題 4.2から $A\in\mathsf P$ である。したがって $\mathsf{NP}\subseteq\mathsf P$ であり、二つのクラスは等しい。▨

3 有界計算表

Cook–Levin の帰着では、帰着元の言語ごとに非決定性機械 $N$ を一つ固定する。入力 $x$ だけが帰着関数の入力であり、 $N$ の状態集合、テープアルファベット、遷移規則は式サイズに対する定数として扱われる。

$N$ を一方向無限の単テープ非決定性 Turing 機械とする。§E15.11 命題 1.3により、NP の定義で用いた読取り専用入力テープと作業テープのモデルから、この標準単テープモデルへ変更しても多項式時間性と受理分枝の存在は保たれる。

長さ $n$ の入力上の全分枝が $p(n)$ 段以内に停止するとする。

T(n)=\max\{p(n),n,1\}

と置く。固定多項式 $p$ の値を二進筆算で求めて $n,1$ と比較することにより、 $T(n)$ は $n$ から多項式時間で計算することができる。また、

T(n)\le p(n)+n+1

であるため、 $T(n)$ は $n$ の多項式で上から抑えられる。受理または拒否で早く停止した配置には、記号、ヘッド位置、状態を変えない仮想的な停止後遷移を加える。この規約は受理分枝の有無を変えず、すべての分枝をちょうど $T(n)$ 段の配置列へ延長する。

テープアルファベットを $\Gamma$ 、状態集合を $Q$ とし、

\mathcal A=\Gamma\cup(Q\times\Gamma)

をセル記号集合とする。 $a\in\Gamma$ はヘッドがないセルの内容を表し、 $(q,a)\in Q\times\Gamma$ は状態が $q$ でヘッドがそのセルを走査し、セル内容が $a$ であることを表す。

時刻 $t$ と位置 $i$ が $0\le t,i\le T=T(n)$ を満たす格子を考える。初期ヘッドは位置 $0$ にあり、一段で高々一マス動くため、時刻 $T$ までの実際の計算が位置 $T$ より右へ到達することはない。

定義 3.1 (計算表変数). 各 $0\le t,i\le T$ と $a\in\mathcal A$ に対して Boolean 変数

X_{t,i,a}

を置く。 $X_{t,i,a}=1$ は、時刻 $t$ 、位置 $i$ のセル記号が $a$ であることを表す。

さらに、 $N$ の有限な遷移規則集合を $\mathcal R$ とし、各 $0\le t<T$ と $d\in\mathcal R$ に対して変数

C_{t,d}

を置く。 $C_{t,d}=1$ は、時刻 $t$ から $t+1$ への遷移で規則 $d$ を選ぶことを表す。停止後の仮想的な自己遷移も $\mathcal R$ に含める。これらの Boolean 変数を総称して計算表変数 (computation-tableau variable) という。

遷移選択変数を時刻ごとに一つ置くことにより、非決定的な二つの規則を隣接セルが別々に選ぶ誤った計算表を排除する。

4 CNF 制約の構成

有限集合の変数 $u_1,\ldots,u_m$ のうちちょうど一つを真にする条件は、CNF

(u_1\lor\cdots\lor u_m) \land \bigwedge_{1\le r<s\le m}(\neg u_r\lor\neg u_s)

で表すことができる。この形式を以下で繰り返し用いる。

4.1 セルとヘッドの一意性

各 $(t,i)$ について、 $a\in\mathcal A$ にわたる $X_{t,i,a}$ のうちちょうど一つが真であるという節を加える。また、各時刻 $t$ について

\{X_{t,i,(q,a)}:0\le i\le T,\ q\in Q,\ a\in\Gamma\}

のうちちょうど一つが真であるという節を加える。後者は、各行にヘッドと状態の印がちょうど一つ存在することを保証する。

4.2 初期配置

入力 $x=x_0\cdots x_{n-1}$ に対し、時刻 $0$ の各セルを単位節で固定する。 $n>0$ なら位置 $0$ を $(q_0,x_0)$ 、位置 $1,\ldots,n-1$ をそれぞれ $x_i$ 、位置 $n,\ldots,T$ を空白記号 $\sqcup$ とする。 $n=0$ なら位置 $0$ を $(q_0,\sqcup)$ とし、残りを空白にする。

4.3 遷移規則の一意性と適用可能性

各 $0\le t<T$ について、 $d\in\mathcal R$ にわたる $C_{t,d}$ のうちちょうど一つが真であるという節を加える。規則 $d$ の左辺が状態 $q$ と走査記号 $a$ でない場合には、各位置 $i$ について

\neg X_{t,i,(q,a)}\lor\neg C_{t,d}

を加える。各行にはヘッド印が一つだけ存在するため、真に選ばれた規則はその配置へ適用することができる規則に限られる。

4.4 局所更新

規則 $d$ を固定する。位置 $i$ の次のセル記号は、時刻 $t$ の位置 $i-1,i,i+1$ の三つのセル記号と $d$ だけから一意に定まる。実際、ヘッドが三セルの外にあれば中央セルは変化しない。ヘッドが中央にあれば、書込み記号と移動方向に従って中央の印を消すか残す。ヘッドが左隣から右へ、または右隣から左へ移る場合には、中央セルへ新状態の印を付ける。位置 $0$ で左移動を命じた場合には、ヘッドは位置 $0$ にとどまる。

この局所更新関数を

F_d\colon\mathcal A^3\longrightarrow\mathcal A

と書く。規則 $d$ が三セル内のヘッド印へ適用することができない組や、複数のヘッド印を含む組には、 $F_d$ の値を任意に定めて全域関数にする。実際の行ではヘッド印と規則の適用可能性を別の節が保証するため、適用不能な組に割り当てた任意の値は充足可能性に影響しない。

左端の外側にはセル記号集合 $\mathcal A$ に属さない固定境界記号 $\triangleleft$ を置く。左端専用の局所更新関数

F_d^{\mathrm L}\colon\mathcal A^2\longrightarrow\mathcal A

を、現在の位置 $0,1$ のセル記号から位置 $0$ の次のセル記号を返す関数として定める。この関数では、位置 $0$ で左移動を命じられたヘッドを位置 $0$ にとどめる。適用することができない組には値を任意に定めて全域関数にする。 $t<T$ ではヘッド位置が高々 $t$ であるため、位置 $T+1$ はまだ訪問されていない。そこで、位置 $T$ の右隣には固定空白記号を置いて $F_d$ を用いる。

各 $0\le t<T$ 、 $1\le i<T$ 、 $d\in\mathcal R$ 、および三つのセル記号 $a_{-1},a_0,a_{+1}\in\mathcal A$ に対して、含意

C_{t,d}\land X_{t,i-1,a_{-1}}\land X_{t,i,a_0}\land X_{t,i+1,a_{+1}} \ \Longrightarrow\ X_{t+1,i,F_d(a_{-1},a_0,a_{+1})}

を CNF の一つの節

\neg C_{t,d}\lor \neg X_{t,i-1,a_{-1}}\lor \neg X_{t,i,a_0}\lor \neg X_{t,i+1,a_{+1}}\lor X_{t+1,i,F_d(a_{-1},a_0,a_{+1})}

として加える。左端 $i=0$ では、各 $a_0,a_{+1}\in\mathcal A$ に対して

\neg C_{t,d}\lor \neg X_{t,0,a_0}\lor \neg X_{t,1,a_{+1}}\lor X_{t+1,0,F_d^{\mathrm L}(a_0,a_{+1})}

を加える。右端 $i=T$ では、各 $a_{-1},a_0\in\mathcal A$ に対して

\neg C_{t,d}\lor \neg X_{t,T-1,a_{-1}}\lor \neg X_{t,T,a_0}\lor X_{t+1,T,F_d(a_{-1},a_0,\sqcup)}

を加える。各行のセル記号が一意であるため、実際の三セルの値に対応する節だけが次行の値を強制する。

4.5 受理条件

時刻 $T$ に受理状態の印が存在するという一つの節

\bigvee_{\substack{0\le i\le T\\a\in\Gamma}} X_{T,i,(q_{\mathrm{acc}},a)}

を加える。停止後の自己遷移によって、時刻 $T$ で受理状態にあることは、時刻 $T$ 以前に受理したことと同値である。

以上のすべての節の論理積を

\Phi_{N,x}

とする。

5 計算表と充足割当の同値性

補題 5.1. 時刻 $t$ と $t+1$ の二行がセル・ヘッドの一意性を満たし、時刻 $t$ で選ばれた規則 $d$ が唯一のヘッド印へ適用可能であるとする。この二行がすべての局所更新節を満たすことと、第二行が規則 $d$ による第一行の正しい次配置であることは同値である。

証明. 第二行が正しい次配置なら、内点 $1\le i<T$ のセル記号は $F_d(a_{i-1},a_i,a_{i+1})$ 、左端のセル記号は $F_d^{\mathrm L}(a_0,a_1)$ 、右端のセル記号は $F_d(a_{T-1},a_T,\sqcup)$ である。したがって、前件が真になる局所更新節の後件も真であり、他の局所更新節は前件の少なくとも一つのリテラルが偽である。よってすべての節が満たされる。

逆に、すべての局所更新節が満たされるとする。内点 $1\le i<T$ では、一意性によって第一行の位置 $i-1,i,i+1$ の実際のセル記号 $a_{i-1},a_i,a_{i+1}$ が一つずつ定まる。選択規則も $d$ に一意に定まるため、実際の三セル記号と選択規則 $d$ を前件とする節ではすべての否定リテラルが偽になり、

X_{t+1,i,F_d(a_{i-1},a_i,a_{i+1})}=1

でなければならない。同じ議論を左端では実際の二セル $a_0,a_1$ と $F_d^{\mathrm L}$ に、右端では実際の二セル $a_{T-1},a_T$ と $F_d(a_{T-1},a_T,\sqcup)$ に適用する。第二行の各位置におけるセル記号も一意であるため、第二行の唯一のセル記号は対応する局所更新関数が指定した記号に等しい。対応する等式がすべての位置で成り立つので、第二行は規則 $d$ による正しい次配置である。▨

定理 5.2. 任意の入力 $x$ について、

N\text{ が }x\text{ を受理する} \quad\Longleftrightarrow\quad \Phi_{N,x}\text{ は充足可能である}.

証明. $N$ が $x$ を受理するとする。受理分枝を一つ選び、停止後の自己遷移によって長さ $T$ まで延長する。各時刻と位置について、その計算表に実際に現れるセル記号に対応する $X$ だけを真にする。各時刻で実際に選ばれた遷移規則に対応する $C$ だけを真にする。

各セルには一つの記号があり、各配置には一つのヘッドがあるため、一意性制約を満たす。時刻 $0$ は初期配置制約を満たし、選んだ規則は実際に適用した規則なので適用可能性制約を満たす。連続する二行は正しい一段遷移であるため、補題 5.1により局所更新制約を満たす。分枝は時刻 $T$ までに受理し、その後は受理配置にとどまるので受理節も満たす。したがって $\Phi_{N,x}$ は充足可能である。

逆に、 $\Phi_{N,x}$ を満たす割当が存在するとする。セル一意性により、各 $(t,i)$ にはセル記号が一つ定まり、ヘッド一意性により各行は状態とヘッド位置を一つもつ配置を表す。初期配置節により第 $0$ 行は $N(x)$ の初期配置である。

各 $t<T$ では遷移選択制約により規則 $d_t$ が一つ定まる。適用可能性節により $d_t$ は第 $t$ 行の状態と走査記号へ適用することができる。補題 5.1により、第 $t+1$ 行は $d_t$ による第 $t$ 行の正しい次配置である。 $t$ に関する帰納法によって、全行が初期配置から始まる一つの実在する計算分枝をなす。受理節により最終行の状態は $q_{\mathrm{acc}}$ であるため、この分枝は $x$ を受理する。▨

6 式サイズと帰着の計算時間

補題 6.1. $N$ を固定すると、 $\Phi_{N,x}$ の変数数、節数、符号長、および $\Phi_{N,x}$ を出力する時間は、 $T(|x|)$ の多項式である。

証明. $|\mathcal A|$ と $|\mathcal R|$ は固定機械 $N$ だけに依存する定数である。セル変数は

(T+1)^2|\mathcal A|=O(T^2)

個であり、遷移選択変数は $T|\mathcal R|=O(T)$ 個である。

セル記号の一意性には各セル当たり定数個の節しか要らないため、節数は $O(T^2)$ である。ヘッドの存在には各行一つ、ヘッドの一意性には各行で $O(T^2)$ 個の二リテラル節を用いるため、全体で $O(T^3)$ 個である。遷移選択、初期配置、適用可能性、および局所更新の節数は、各時刻・位置と固定有限集合を走査して作るので $O(T^2)$ 個である。受理条件は一つの長い節であり、リテラル数は $O(T)$ である。

したがって節とリテラルの総数は $O(T^3)$ である。添字 $t,i$ を二進表記する変数名には $O(\log(T+2))$ ビットを要するため、式全体の符号長は

O\bigl(T^3\log(T+2)\bigr)

である。

帰着機械は入力長 $n$ から固定多項式 $T(n)$ を計算し、上で列挙した順に変数名と節を書き出す。各節の生成には添字に関する多項式時間しか要らず、出力長自体も $T$ の多項式である。 $T(n)$ は $n$ の多項式なので、出力時間と出力長はいずれも $n$ の多項式である。▨

7 Cook–Levin の定理

定理 7.1 (Cook–Levin の定理). 充足可能性問題 $\mathsf{SAT}$ は NP 完全である。

証明.命題 1.2により、 $\mathsf{SAT}\in\mathsf{NP}$ である。

任意の言語 $A\in\mathsf{NP}$ をとる。§E15.11 定義 1.2により、 $A$ を受理する多項式時間非決定性 Turing 機械 $N$ が存在する。 $N$ を固定し、入力 $x$ に対して

f(x)=\langle\Phi_{N,x}\rangle

と定める。補題 6.1により、 $f$ は多項式時間で計算される。定理 5.2により、

x\in A \Longleftrightarrow N\text{ が }x\text{ を受理する} \Longleftrightarrow \Phi_{N,x}\text{ は充足可能である} \Longleftrightarrow f(x)\in\mathsf{SAT}.

したがって $A\le_{\mathrm p}\mathsf{SAT}$ である。 $A\in\mathsf{NP}$ は任意であったため、 $\mathsf{SAT}$ は NP 困難である。NP への所属と合わせて、 $\mathsf{SAT}$ は NP 完全である。▨

例 7.2 (小さな CNF の充足割当). CNF

(z_1\lor z_2)\land(\neg z_1\lor z_2)

を考える。割当 $(z_1,z_2)=(0,1)$ では二つの節がともに真になり、式全体が真になる。 $(1,0)$ では第二節が偽になる。

計算表の符号化でも、各節は同じように許されない局所選択を排除する。一意性節は二つのセル記号を同時に選ぶ割当を排除し、局所更新節は前の三セルと選択規則が定まったときに誤った次セルを選ぶ割当を排除する。個々の節は局所的であるが、すべての節の論理積が計算表全体の整合性を保証する。

8 つまずいたら

SAT が NP 完全であることは、SAT が P に属さないことを意味しない。SAT が P に属するかどうかは $\mathsf P=\mathsf{NP}$ と同値な未解決問題である。
計算表では、各セルの記号だけでなく、各行のヘッドと状態、および各時刻の非決定的な遷移選択を一意にする必要がある。
局所更新節だけでは初期配置と受理を保証しない。初期配置節と最終行の受理節を別に加える必要がある。
帰着先の式が大きくても、入力長の多項式で抑えられていれば多項式時間帰着である。機械 $N$ の状態数とアルファベットサイズは、帰着元の言語を固定した時点で定数になる。
本記事の出力は CNF であるが、各節のリテラル数を三つ以下には制限していない。3SAT の NP 完全性には、節幅を制限する別の多項式時間変換と、その充足可能性保存の完全な証明が必要である。

9 演習

問題 9.1.

命題 1.2の検証器について、変数名が二進添字で符号化される場合にも証明書長が入力長以下になる理由を説明せよ。
各時刻で遷移選択変数 $C_{t,d}$ を一つに定めず、各セルが独立に非決定的規則を選ぶと、正当な計算分枝に対応しない表が生じ得る理由を説明せよ。
補題 5.1の逆向きの証明で、セル記号の一意性が必要な箇所を特定せよ。
ヘッドの一意性を素朴な二変数節で表した場合に $O(T^3)$ 個の節を要することを計算せよ。節数が $O(T^3)$ であっても帰着が多項式時間である理由を述べよ。
早く受理した配置を停止後の自己遷移で延長する規約が、受理分枝の有無を変えないことを証明せよ。

解答 (演習の要点).

証明書は、式に現れる相異なる変数それぞれに対する一ビットである。各変数は式の符号の中で少なくとも一文字を占めるので、相異なる変数の個数は符号長 $m$ 以下である。したがって証明書長も $m$ 以下であり、入力長の多項式である。二進添字を用いる符号では一つの変数が複数文字を占めるため、変数の個数はさらに小さくなる。
一つの配置から次の配置への遷移は、ただ一つの規則によって定まる。セルごとに独立に規則を選ぶことを許すと、ある位置は規則 $d$ の局所更新に従い、別の位置は規則 $d'$ の局所更新に従う行が現れる。たとえば、 $d$ がヘッドの右移動を、 $d'$ が左移動を命じる場合、次の行のヘッド印の位置は $d$ と $d'$ のどちらの配置とも一致しない。局所条件はすべて満たされていても、その行は $N$ のどの一段遷移の結果でもない。
二箇所で用いる。第一に、第一行の位置 $i-1,i,i+1$ の記号がそれぞれ一つに定まることを用いて、否定リテラルがすべて偽になる局所更新節をちょうど一つ特定する箇所である。一意性がなければ、複数の三つ組に対応する節が同時に前件を満たし、互いに異なる後件を強制することがあり得る。第二に、第二行の位置 $i$ の記号が一つに定まることを用いて、強制された $X_{t+1,i,F_d(\cdots)}=1$ からその位置の記号が $F_d(\cdots)$ に等しいと結論する箇所である。
各行のヘッド印の候補は、位置 $0\le i\le T$ と $(q,a)\in Q\times\Gamma$ の組であり、 $|Q||\Gamma|$ が定数なので $O(T)$ 個である。そのうち二つを選ぶ組は $O(T^2)$ 個であり、行は $T+1$ 個あるから、全体で $O(T^3)$ 個の二変数節を要する。 $T(n)$ は $n$ の多項式であるから $O(T^3)$ も $n$ の多項式であり、各節の書き出しに要する時間も添字に関する多項式である。したがって帰着関数は多項式時間で計算される。
停止後の自己遷移は記号、ヘッド位置、状態のいずれも変えない。したがって、時刻 $t_0\le T$ で受理状態に到達した分枝は時刻 $T$ まで受理状態にとどまり、延長後の分枝は時刻 $T$ で受理状態にある。逆に、延長後の分枝が時刻 $T$ で受理状態にあるとする。自己遷移は状態を変えないので、受理状態に初めて入る時刻 $t_0$ が存在し、時刻 $t_0$ までの配置列は自己遷移を含まない。よって、それは元の機械の受理分枝である。ゆえに、延長の前後で受理分枝の有無は変わらない。

▨

§E15.12NP 完全性と Cook–Levin の定理

1 Boolean 論理式と SAT

2 NP 困難性と NP 完全性

3 有界計算表

4 CNF 制約の構成

4.1 セルとヘッドの一意性

4.2 初期配置

4.3 遷移規則の一意性と適用可能性

4.4 局所更新

4.5 受理条件

5 計算表と充足割当の同値性

6 式サイズと帰着の計算時間

7 Cook–Levin の定理

9 演習

参考文献

前提記事