Aritalab:Lecture/Algorithm/CooksTheorem
m (New page: ==クックの定理== クックは1971年に論理式の充足可能性問題がNP完全であることを証明しました。 ;参考文献 : Garey MR, Johnson DS "Computers and Intract...) |
(→Cookの定理) |
||
| Line 22: | Line 22: | ||
SATがNPに入ることは明らかです。正解となる論理変数の割り当てを知っていれば、節が充足されることを検証するのは簡単です（線形時間しか要しません）。 | SATがNPに入ることは明らかです。正解となる論理変数の割り当てを知っていれば、節が充足されることを検証するのは簡単です（線形時間しか要しません）。 | ||
| − | + | SATがNP完全であることを示すには、NPに属するあらゆる問題が、SATの一例とみなせることを示さなくてはなりません。しかし、あらゆるNP問題を逐一SATに変換していては埒が明きません。 | |
| − | + | ||
| − | + | ||
そのかわり、非決定性チューリング機械 (NDTM) の全動作パターンを、SATで特定できることを示します。 | そのかわり、非決定性チューリング機械 (NDTM) の全動作パターンを、SATで特定できることを示します。 | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | 入力文字列を x 、計算が終わるまでに必要な多項式時間ステップを p(n) (n = |X|) とします （受理状態も含めます）。 この時間内で、NDTM ''M'' = (Γ, Q, δ, x) はテープ位置 -p(n) から p(n) + 1 の内側しか処理できないことを利用します。''M'' の状態数やテープ記号数も有限ですから、これらに関する処理を有限個の変数で記述することが可能です。 | |
{| class="wikitable" | {| class="wikitable" | ||
| − | ! 変数 || 意味 || | + | ! 変数 || 意味 || パラメータ || 大雑把な個数 |
|- | |- | ||
| − | | Q<sub>i,k</sub> || 時間 i | + | | Q[t<sub>i</sub>, q<sub>k</sub>] || 時間 i において ''M'' が状態 q<sub>k</sub>にある時に限り True |
| − | | 0 ≤ i ≤ p(n)<br/>0 ≤ k ≤ | + | | 0 ≤ i ≤ p(n)<br/>0 ≤ k ≤ |Q| |
| + | | p(n) * |Q| | ||
|- | |- | ||
| − | | H<sub>i | + | | H[t<sub>i</sub>, j] || 時間 i において ''M'' のヘッドがテープ位置 j にある時に限り True |
| 0 ≤ i ≤ p(n)<br/>-p(n) ≤ j ≤ p(n) + 1 | | 0 ≤ i ≤ p(n)<br/>-p(n) ≤ j ≤ p(n) + 1 | ||
| + | | 2 p(n)<sup>2</sup> | ||
|- | |- | ||
| − | | S<sub>i,j,k</sub> || 時間 i においてテープ位置 j に記号 s<sub>k</sub> が書かれている時に限り | + | | S[t<sub>i</sub>, j, s<sub>k</sub>] || 時間 i においてテープ位置 j に記号 s<sub>k</sub> が書かれている時に限り True |
| − | | 0 ≤ i ≤ p(n)<br/>-p(n) ≤ j ≤ p(n) + 1<br/>0 ≤ k ≤ | + | | 0 ≤ i ≤ p(n)<br/> -p(n) ≤ j ≤ p(n) + 1<br/>0 ≤ k ≤ |Γ| |
| + | | 2 p(n)<sup>2</sup> * |Γ| | ||
|} | |} | ||
Revision as of 11:13, 31 October 2010
クックの定理
クックは1971年に論理式の充足可能性問題がNP完全であることを証明しました。
- 参考文献
- Garey MR, Johnson DS "Computers and Intractability" WH Freeman & Co. 1979
論理式の充足可能性問題
ブール変数の集合 U = { u1, u2 ... um } に対する真偽の割り当て t: U → {T, F} を考えます。変数が m 個あれば、割り当てパターンは 2m 通りあります。 U に含まれる複数個のブール変数 u またはその否定 ￢u を ∨ (or) でつないだものを節といいます。 節が真になるとき、その節は充足されたといいます。 例えば{ u1, ￢u3, u8 } という節は、 u1 = F かつ u3 = T かつ u8 = F でない限り充足されます。（充足する真偽の割り当ては7パターンあります。）
節の集合 C が充足可能であるとは、C に含まれる節を全て充足するようなブール変数の集合 U に対する真偽の割り当て t が存在することをいいます。この定義を用いて、充足可能性問題 (SAT: Satisfiability Problem) は以下のように書けます。
- 「変数の集合 U 上の節集合 C に対して、それを充足する真偽の割り当てが存在するか？」
例えばU = { u1, u2 } において
- C = { {￢u1, u2}, {u1, ￢u2} } は充足可能 ( u1 = u2 = T のとき)
- C = { {￢u1, u2}, {u1, ￢u2}, {￢u1} } は充足不可能
となります。充足可能性を判定するには、2m 通りに近い真偽パターンを試す以外に方法が無いと考えられています。
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 の状態数やテープ記号数も有限ですから、これらに関する処理を有限個の変数で記述することが可能です。
| 変数 | 意味 | パラメータ | 大雑把な個数 |
|---|---|---|---|
| Q[ti, qk] | 時間 i において M が状態 qkにある時に限り True | 0 ≤ i ≤ p(n) 0 ≤ k ≤ |Q| |
p(n) * |Q| |
| 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 ≤ |Γ| |
2 p(n)2 * |Γ| |
