Aritalab:Lecture/Algorithm/CooksTheorem

注：このページを理解するためには、P, NP という問題クラスの概念とチューリングマシンの知識が必要です。

クックの功績

クック　(Stephen Cook) は1971年に論理式の充足可能性問題がNP完全であることを証明しました。 この論文が計算量理論にもたらした功績は複数あります。

• 問題を多項式時間で変換することの重要性を説いた
• 非決定性の判定問題に焦点を当てた
• 充足可能性問題がNP完全であることを証明した

この功績により、クックはTuring賞を受賞しています。

参考文献 

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

論理式の充足可能性問題

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

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

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

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

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

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

となります。充足可能性を判定するには、2^m 通りに近い真偽パターンを試す以外に方法が無さそうです。それゆえNP完全、クラスNPの中でも最も難しいとされる問題クラスに属しています。（ただしP ≠ NP は証明されていません。） 充足可能性は英語で SATISFIABILITY なので、SAT問題と呼ばれます。

クックの定理

充足可能性問題 (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 ... 空白記号 (b = s₀とする) や入力記号も含めた、テープ記号数 | Γ | のこと

です。 r や v は　NDTM の構造で決まる定数とみなせるので、変数の総数は　p(n)² オーダーであることがわかります。

これらの変数を用いて次表に示す6つの節グループを作成し、NDTM M の動きを規定しましょう。

グループ	意味	節の構成	変数の範囲	節の個数（大雑把に）
1. 状態に関する制約	時刻 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
2. ヘッド位置に関する制約	時刻 i においてヘッドはいずれかのテープ位置にある	{ H [ ti, −p(n) ], H [ ti, −p(n)+1 ], ..., H [ ti, p(n)+1 ] }	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
3. テープに書く記号に関する制約	時刻 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
4. M の初期設定に関する制約	時間0の初期状態では、テープが左端でヘッドは空白記号をみている	{ Q [ t0, q0 ] }, { H [ t0, 1 ] }, { S [ t0, 0, s0 ] }	-	3
	テープに入力 x = k1k2...knのみ書かれている	{ S [ t0, 1, k1 ] }, { S [ t0, 2, k2 ] }, u... { S [ t0, n, kn ] }, { S [ t0, n+1, b ] }, { S [ t0, n+2, b ] }, ... { S [ t0, p(n)+1, b ] }	-	p(n)
5. 受理状態に関する制約	時刻 p(n) には M が状態 qY に到達	{ Q [ tp(n), qY ] }	-	1
6. 状態遷移に関する制約	時刻 i にテープ位置 j をアクセスしない場合 j の中身はslのまま変化しない	{ ￢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 における状態遷移が δ(qk,sl) = (qk',sl',Δ) で表現される	{ ￢H[ ti, j ], ￢Q[ ti, qk ], ￢S[ ti, j, sl ], H[ ti+1, j + Δ ] } { ￢H[ ti, j ], ￢Q[ ti, qk ], ￢S[ ti, j, sl ], Q[ ti+1, qk' ] } { ￢H[ ti, j ], ￢Q[ ti, qk ], ￢S[ ti, j, sl ], S[ ti+1, j, sl' ] }	0 ≤ i < p(n), −p(n) ≤ j ≤ p(n) + 1, 0 ≤ k ≤ r, 0 ≤ l ≤ v	6 * p(n)2* r * v

節の解釈

表中にでてくる節の形には大きく分けて以下の5パターンあります。

1. { L₁, L₂, ... L_k } 

この形は、どれか一つでもTrueであれば満たされるので、選択肢を記述するために使われます。

2. { ￢L₁, ￢L₂ } 

この形は、両方が真であるときに限り満たせないので、選択肢の排他性を記述するために使われます。

表のうちグループ1からグループ3までの制約はこの2パターンで書かれています。

3. { L } 

この形は L が必ず True であることを意味します。初期設定や受理状態など、グループ4とグループ5の制約がこのパターンで書かれています。

4. { ￢L₁,　L₂, L₃ } 

この形は、( if not L₂ then L₁ → L₃ ) という論理式に読みかえられます。

5. { ￢L₁,　￢L₂, ￢L₃, L₄ } 

この形は、( L₁ ∧ L₂ ∧ L₃ → L₄ ) という論理式に読みかえられます。こうするとグループ6に属す節は以下の内容を記述していることがわかります。

• if not H [ t_i, j ] → (S [ t_i, j, s_l ] → S [ t_i+1, j, s_l ])
  もしヘッドがテープ位置 j を見ていないなら、テープ位置の内容 s_l は時刻 i+1 になっても　s_l のまま
• (H[ t_i, j ] ∧ Q[ t_i, q_k ] ∧ S[ t_i, j, s_l ]) → H[ t_i+1, j + Δ ] (Q, Sも同様)
  もしヘッドがテープ位置 j で状態　(q_k,s_l) を満たすなら、時刻 i+1 には状態は (q_k',s_l') となり、ヘッドはΔ移動する

表に出てくる節の個数は p(n)³ のオーダーで抑えられますし、各節の中には p(n) オーダーの変数しか現れません。 結果として、いかなる NDTM のプログラムを与えられても、プログラムの全動作を入力文字列　p(n)⁴ オーダーのSAT問題として記述できることがわかりました。

NP完全性のインパクト

クックの定理から以下のことがわかります。

問題 x がクラスNPに属する	⇔	定義より、x に多項式時間でYESという NDTM のプログラムが存在
	⇔	クックの定理により NDTM の入力とプログラムを多項式時間で変換したSAT問題が存在

つまり、SAT問題の表現能力はクラスNPに属する全ての問題を包含しているのです。そのため、どんなSAT問題を与えられても多項式時間で解くアルゴリズムがあるとするならば、クラス NP に属する全ての問題をO(p(n)⁴)時間でSAT問題に変換することで、それらを多項式時間で解くことになります。つまり、SAT問題は NP に属するどの問題と比較しても同等以上に難しい、NP完全であることが示されています。

SAT問題と3-SAT問題

SAT問題は複雑な論理式が多く使われており、解くのが十分に難しそうです。しかし、各節にリテラルをちょうど3つしか含まないように制約を設けた3-SATISFIABILITYもNP完全であることが簡単に示せます。

3-SAT問題はNP完全

3-SATを充足させる変数の T, F が与えられたらすぐにYESと判断できるため、3-SAT ∈ NP です。 ここで SAT から 3-SAT への変換を考えます。SATにおける各節 C を以下のように変換します。

• 変数を1個含む場合 C = { z }

C にしか使わない変数を二つ x₁, x₂ 用意し、次の4節で置き換えます。 { { z, x₁, x₂ } ∧ { z, ¬x₁, x₂ } ∧ { z, x₁, ¬x₂ } ∧ { z, ¬x₁, ¬x₂ } }

• 変数を2個含む場合 C = { z₁, z₂ }

C にしか使わない変数 x を用意し、次の2節で置き換えます。 { { z₁, z₂, x } ∧ { z₁, z₂, ¬x } }

• 変数を3個含む場合はそのまま使います。

• 変数を k (> 3) 個含む場合 C = { z₁, z₂, ... z_k }

C にしか使わない変数を k−3 個用意し { x₁, x₂, ... x_k-3 } 、次の k−2 節で置き換えます。

C' = { { z₁, z₂, x₁ } ∧ { ¬x₁, z₃, x₂ } ∧ { ¬x₂, z₄, x₃ } } ... ∧ { ¬x_k-3, z_k-1, z_k } }

もとの節に含まれる変数の数が 3 個以下の場合、上記の変換において、もとの節における変数のアサインメントで充足可能 ⇔ 置き換えた節が充足可能　であることがすぐにわかります。 新しく導入する変数のアサインメントは T でも F でもよいからです。変数を k 個含むときだけ少し面倒です。

もとの節　C = { z₁, z₂, ... z_k } が充足可能な時、少なくともある変数 z_m が T になっています。もし m が 1 か 2 の場合は x₁ ... x_k-3 を全て F にすれば、変換後の節 C' が充足されます。もし m が k−1 か k の場合は、x₁ ... x_k-3 を全て T にすれば節 C' が充足されます。もし m が l の場合は、 x₁ ... x_l-2 をすべて T にし、 x_l-1 ... x_k-3 を全て F にすれば C' が充足されます。 T となるリテラルが1個以上の場合は T の数が増えるだけなので、C' の充足性に変化はありません。

逆に、置き換えた節 C' が充足可能である時は、必ず z₁ ... z_k のいずれかが T にならざるを得ませんから（背理法ですぐに証明できます）、もとの節 C が充足可能になります。

以上をまとめると、任意のSAT問題を与えられたら、節の数とほぼ同数の変数を追加に用意するだけで等価な 3-SAT 問題を構成できることが示せました。 このように問題を変換 (reduce) することで、様々な問題がNP完全であることを証明できます。重要な組み合わせ問題に対してこれをCookの定理の翌年に示したのが、現在はバイオインフォマティクスを研究している Richard M Karp でした。