Aritalab:Lecture/Algorithm/CooksTheorem
注：このページを理解するためには、P, NP という問題クラスの概念とチューリングマシンの知識が必要です。
Contents |
クックの功績
クック (Stephen Cook) は1971年に論理式の充足可能性問題がNP完全であることを証明しました。 この論文が計算量理論にもたらした功績は複数あります。
- 問題を多項式時間で変換することの重要性を説いた
- 非決定性の判定問題に焦点を当てた
- 充足可能性問題がNP完全であることを証明した
この功績により、クックはTuring賞を受賞しています。
- 参考文献
- Garey MR, Johnson DS "Computers and Intractability" WH Freeman & Co. 1979
論理式の充足可能性問題
ブール変数の集合 U = { u1, u2 ... um } に対する真偽の割り当て U → {T, F} を考えます。変数が m 個あれば、割り当てパターンは 2m 通りあります。 U に含まれる複数個のブール変数 u またはその否定 ￢u を論理和 (or) ∨ でつないだものを節といいます。 節が真になるとき、その節は充足されたといいます。 例えば{ u1, ￢u2, u3 } という節は、 u1 = F かつ u2 = T かつ u3 = F でない限り充足されます。（充足する真偽の割り当ては7パターンあります。）
節の集合 C が充足可能であるとは、C に含まれる節を全て充足するようなブール変数の集合 U に対する真偽の割り当てが存在することをいいます。この定義を用いて、充足可能性問題 (SAT: Satisfiability Problem) は以下のように書けます。
- 「変数の集合 U 上の節集合 C に対して、それを充足する真偽の割り当てが存在するか？」
例えばU = { u1, u2 } において
- C = { {￢u1, u2}, {u1, ￢u2} } は充足可能 ( u1 = u2 = T のとき)
- C = { {u1, u2}, {u1, ￢u2}, {￢u1} } は充足不可能
となります。充足可能性を判定するには、2m 通りに近い真偽パターンを試す以外に方法が無さそうです。それゆえNP完全、クラスNPの中でも最も難しいとされる問題クラスに属しています。（ただしP ≠ NP は証明されていません。）
クックの定理
- 充足可能性問題 (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 の状態数やテープ記号数も有限ですから、これらに関する処理を有限個の変数で記述することが可能です。
| 変数 | 意味 | パラメータ | 大雑把な個数 |
|---|---|---|---|
| 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 ... 初期状態 q0、受理状態 qY, qN も含めた全状態数 |Q| のこと、
- v ... 空白記号 (b = s0とする) や入力記号も含めた、テープ記号数 | Γ | のこと
です。 r や v は NDTM の構造で決まる定数とみなせるので、変数の総数は p(n)2 オーダーであることがわかります。
これらの変数を用いて次表に示す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. { L1, L2, ... Lk }
- この形は、どれか一つでもTrueであれば満たされるので、選択肢を記述するために使われます。
- 2. { ￢L1, ￢L2 }
- この形は、両方が真であるときに限り満たせないので、選択肢の排他性を記述するために使われます。
表のうちグループ1からグループ3までの制約はこの2パターンで書かれています。
- 3. { L }
- この形は L が必ず True であることを意味します。初期設定や受理状態など、グループ4とグループ5の制約がこのパターンで書かれています。
- 4. { ￢L1, L2, L3 }
- この形は、( if not L2 then L1 → L3 ) という論理式に読みかえられます。
- 5. { ￢L1, ￢L2, ￢L3, L4 }
- この形は、( L1 ∧ L2 ∧ L3 → L4 ) という論理式に読みかえられます。こうするとグループ6に属す節は以下の内容を記述していることがわかります。
- if not H [ ti, j ] → (S [ ti, j, sl ] → S [ ti+1, j, sl ])
もしヘッドがテープ位置 j を見ていないなら、テープ位置の内容 sl は時刻 i+1 になっても sl のまま - (H[ ti, j ] ∧ Q[ ti, qk ] ∧ S[ ti, j, sl ]) → H[ ti+1, j + Δ ] (Q, Sも同様)
もしヘッドがテープ位置 j で状態 (qk,sl) を満たすなら、時刻 i+1 には状態は (qk',sl') となり、ヘッドはΔ移動する
表に出てくる節の個数は p(n)3 のオーダーで抑えられますし、各節の中には p(n) オーダーの変数しか現れません。 結果として、いかなる NDTM のプログラムを与えられても、プログラムの全動作を入力文字列 p(n)4 オーダーのSAT問題として記述できることがわかりました。
NP完全性のインパクト
クックの定理から以下のことがわかります。
| 問題 x がクラスNPに属する | ⇔ | 定義より、x に多項式時間でYESという NDTM のプログラムが存在 |
| ⇔ | クックの定理により NDTM の入力とプログラムを多項式時間で変換したSAT問題が充足可能 |
どんなSAT問題を与えられても多項式時間で解けてしまうアルゴリズムがあるとするならば、クラス NP に属する全ての問題をO(p(n)4)時間でSAT問題に変換することで、全体が多項式時間で解けることになります。つまり、SAT問題は NP に属するどの問題と比較しても同等以上に難しい、NP完全であることが示されています。
