Aritalab:Lecture/Algorithm/CooksTheorem

クックの定理

クックは1971年に論理式の充足可能性問題がNP完全であることを証明しました。

参考文献 

Garey MR, Johnson DS "Computers and Intractability" WH Freeman & Co. 1979

論理式の充足可能性問題

ブール変数の集合 U = { u₁, u₂ ... u_m } に対する真偽の割り当て t: U → {T, F} を考えます。変数が m 個あれば、割り当てパターンは 2^m 通りあります。 U に含まれる複数個のブール変数 u またはその否定 ￢u を ∨ (or) でつないだものを節といいます。 節が真になるとき、その節は充足されたといいます。 例えば{ u₁, ￢u₂, u₃ } という節は、 u₁ = F かつ u₂ = T かつ u₃ = F　でない限り充足されます。（充足する真偽の割り当ては7パターンあります。）

節の集合 C が充足可能であるとは、C に含まれる節を全て充足するようなブール変数の集合 U に対する真偽の割り当て t が存在することをいいます。この定義を用いて、充足可能性問題 (SAT: Satisfiability Problem) は以下のように書けます。

「変数の集合 U 上の節集合 C に対して、それを充足する真偽の割り当てが存在するか？」

例えばU = { u₁, u₂ } において

C = { {￢u₁, u₂}, {u₁, ￢u₂} } は充足可能 ( u₁ = u₂ = T のとき)

C = { {u₁, u₂}, {u₁, ￢u₂}, {￢u₁} } は充足不可能

となります。充足可能性を判定するには、2^m 通りに近い真偽パターンを試す以外に方法が無いと考えられています。

Cookの定理

充足可能性問題 (SAT) はNP完全である

SATがNPに入ることは明らかです。正解となる論理変数の割り当てを知っていれば、節が充足されることを検証するのは簡単です（線形時間しか要しません）。 SATがNP完全であることを示すには、NPに属するあらゆる問題が、SATの一例とみなせることを示さなくてはなりません。しかし、あらゆるNP問題を逐一SATに変換していては埒が明きません。 そのかわり、非決定性チューリング機械 (NDTM) の全動作パターンを、SATで特定できることを示します。

入力文字列を x 、計算が終わるまでに必要な多項式時間ステップを p(n) (n = |X|) とします　（受理状態も含めます）。 この時間内で、NDTM M = (Γ, Q, δ, x) はテープ位置 -p(n) から p(n) + 1 の内側しか処理できないことを利用します。M の状態数やテープ記号数も有限ですから、これらに関する処理を有限個の変数で記述することが可能です。

+ M の記述に用いる変数

変数	意味	パラメータ	大雑把な個数
Q[ti, qk]	時間 i において M が状態 qkにある時に限り True	0 ≤ i ≤ p(n) 0 ≤ k ≤ r	p(n) * r
H[ti, j]	時間 i において M のヘッドが テープ位置 j にある時に限り True	0 ≤ i ≤ p(n) -p(n) ≤ j ≤ p(n) + 1	2 p(n)2
S[ti, j, sk]	時間 i においてテープ位置 j に 記号 sk が書かれている時に限り True	0 ≤ i ≤ p(n) -p(n) ≤ j ≤ p(n) + 1 0 ≤ k ≤ v	2 p(n)2 * v

r ... 初期状態 q₀、受理状態 q_Y, q_N も含めた全状態数 |Q|

v ... 空白記号や入力記号も含めた、テープ記号数 | Γ |

これらの変数を用いて次表に示す節を作成し、NDTM M の動きを規定します。

グループ	意味	節の構成	変数の範囲	節の個数（大雑把に）
状態に関する制約	時刻 i において M はいずれかの状態にある	{ Q [ ti, q0 ], Q [ ti, qY ], Q [ ti, qN ], Q [ ti, q3 ], ... , Q [ ti, qr ] }	0 ≤ i ≤ p(n)	p(n)
	時刻 i において M は二つの状態を同時に取らない	{ ￢Q [ ti, qj ], ￢Q [ ti, qj' ] }	0 ≤ i ≤ p(n), 0 ≤ j < j' ≤ r	p(n) * r2/2
ヘッド位置に関する制約	時刻 i においてヘッドはいずれかのテープ位置にある	{ H [ ti, -p(n) ], H [ ti, -p(n)+1 ], ..., H [ ti, p(n)+1</sub> ] }	0 ≤ i ≤ p(n)	p(n)
	時刻 i においてヘッドは二つの位置を同時に取らない	{ ￢H [ ti, j ], ￢H [ ti, j' ] }	0 ≤ i ≤ p(n), -p(n) ≤ j < j' ≤ p(n)+1	p(n) * 2 p(n)2
テープに書く記号に関する制約	時刻 i においてテープ位置 j にはいずれかの記号 k がある	{ S [ ti, j, s0 ], S [ ti, j, s1 ], ..., S [ ti, j, sv ] }	0 ≤ i ≤ p(n), -p(n) ≤ j ≤ p(n)+1	p(n) * 2 p(n)
	時刻 i においてテープ位置 j は二種の記号を同時に取らない	{ ￢S [ ti, j, sk ], ￢S [ ti, j, sk' ] }	0 ≤ i ≤ p(n), -p(n) ≤ j ≤ p(n)+1, 0 ≤k < k' ≤ v	p(n) * 2 p(n) * v
M の初期設定に関する制約	初めはテープに入力 x = k1k2...knのみ	{ Q [ t0, q0 ] }, { H [ t0, 1 ] }, { S [ t0, 0, s0 ] }, { S [ t0, 1, k1 ] }, { S [ t0, 2, k2 ] }, ... { S [ t0, n, kn ] }, { S [ t0, n+1, b ] }, { S [ t0, n+2, b ] }, ... { S [ t0, p(n)+1, b ] }	p(n)
受理状態に関する制約	時刻 p(n) には M が状態 qY に到達	{ Q [ tp(n), qY ] }	1
状態遷移に関する制約	時刻 i にテープ j をアクセスしなければ j の中身は i+1 に変化しない	{ ￢S [ ti, j, sl ], H [ ti, j ], S [ ti+1, j, sl ] }	0 ≤ i ≤ p(n), -p(n) ≤ j ≤ p(n)+1, 0 ≤ l ≤ v	2 p(n)2 * v
	時刻 i に