Aritalab:Lecture/Algorithm/CooksTheorem
From Metabolomics.JP
< Aritalab:Lecture | Algorithm(Difference between revisions)
(→Cookの定理) |
m |
||
| Line 7: | Line 7: | ||
U に含まれる複数個のブール変数 u またはその否定 ￢u を ∨ (or) でつないだものを節といいます。 | U に含まれる複数個のブール変数 u またはその否定 ￢u を ∨ (or) でつないだものを節といいます。 | ||
節が真になるとき、その節は充足されたといいます。 | 節が真になるとき、その節は充足されたといいます。 | ||
| − | 例えば{ u<sub>1</sub>, ￢u<sub> | + | 例えば{ u<sub>1</sub>, ￢u<sub>2</sub>, u<sub>3</sub> } という節は、 u<sub>1</sub> = F かつ u<sub>2</sub> = T かつ u<sub>3</sub> = F でない限り充足されます。（充足する真偽の割り当ては7パターンあります。） |
節の集合 C が充足可能であるとは、C に含まれる節を全て充足するようなブール変数の集合 U に対する真偽の割り当て t が存在することをいいます。この定義を用いて、充足可能性問題 (SAT: Satisfiability Problem) は以下のように書けます。 | 節の集合 C が充足可能であるとは、C に含まれる節を全て充足するようなブール変数の集合 U に対する真偽の割り当て t が存在することをいいます。この定義を用いて、充足可能性問題 (SAT: Satisfiability Problem) は以下のように書けます。 | ||
| Line 15: | Line 15: | ||
例えばU = { u<sub>1</sub>, u<sub>2</sub> } において | 例えばU = { u<sub>1</sub>, u<sub>2</sub> } において | ||
: C = { {￢u<sub>1</sub>, u<sub>2</sub>}, {u<sub>1</sub>, ￢u<sub>2</sub>} } は充足可能 ( u<sub>1</sub> = u<sub>2</sub> = T のとき) | : C = { {￢u<sub>1</sub>, u<sub>2</sub>}, {u<sub>1</sub>, ￢u<sub>2</sub>} } は充足可能 ( u<sub>1</sub> = u<sub>2</sub> = T のとき) | ||
| − | : C = { { | + | : C = { {u<sub>1</sub>, u<sub>2</sub>}, {u<sub>1</sub>, ￢u<sub>2</sub>}, {￢u<sub>1</sub>} } は充足不可能 |
となります。充足可能性を判定するには、2<sup>m</sup> 通りに近い真偽パターンを試す以外に方法が無いと考えられています。 | となります。充足可能性を判定するには、2<sup>m</sup> 通りに近い真偽パターンを試す以外に方法が無いと考えられています。 | ||
| Line 28: | Line 28: | ||
{| class="wikitable" | {| class="wikitable" | ||
| + | + ''M'' の記述に用いる変数 | ||
| + | |- | ||
! 変数 || 意味 || パラメータ || 大雑把な個数 | ! 変数 || 意味 || パラメータ || 大雑把な個数 | ||
|- | |- | ||
| Q[t<sub>i</sub>, q<sub>k</sub>] || 時間 i において ''M'' が状態 q<sub>k</sub>にある時に限り True | | 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 ≤ r |
| − | | p(n) * | + | | p(n) * r |
|- | |- | ||
| − | | H[t<sub>i</sub>, j] || 時間 i において ''M'' | + | | H[t<sub>i</sub>, j] || 時間 i において ''M'' のヘッドが<br/>テープ位置 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> | | 2 p(n)<sup>2</sup> | ||
|- | |- | ||
| − | | S[t<sub>i</sub>, j, s<sub>k</sub>] || 時間 i においてテープ位置 j | + | | S[t<sub>i</sub>, j, s<sub>k</sub>] || 時間 i においてテープ位置 j に<br/>記号 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 ≤ v |
| − | | 2 p(n)<sup>2</sup> * & | + | | 2 p(n)<sup>2</sup> * v |
| + | |} | ||
| + | : r ... 初期状態 q<sub>0</sub>、受理状態 q<sub>Y</sub>, q<sub>N</sub> も含めた全状態数 |Q| | ||
| + | : v ... 空白記号や入力記号も含めた、テープ記号数 | Γ | | ||
| + | |||
| + | これらの変数を用いて次表に示す節を作成し、NDTM ''M'' の動きを規定します。 | ||
| + | |||
| + | {| class="wikitable" | ||
| + | ! グループ || 意味 || 節の構成 || 変数の範囲 || 節の個数（大雑把に） | ||
| + | |- | ||
| + | | rowspan="2"| 状態に関する制約 | ||
| + | | 時刻 i において ''M'' はいずれかの状態にある | ||
| + | | { Q [ t<sub>i</sub>, q<sub>0</sub> ], Q [ t<sub>i</sub>, q<sub>Y</sub> ], Q [ t<sub>i</sub>, q<sub>N</sub> ], Q [ t<sub>i</sub>, q<sub>3</sub> ], ... , Q [ t<sub>i</sub>, q<sub>r</sub> ] } | ||
| + | | 0 ≤ i ≤ p(n) | ||
| + | | p(n) | ||
| + | |- | ||
| + | | 時刻 i において ''M'' は二つの状態を同時に取らない | ||
| + | | { ￢Q [ t<sub>i</sub>, q<sub>j</sub> ], ￢Q [ t<sub>i</sub>, q<sub>j'</sub> ] } | ||
| + | | 0 ≤ i ≤ p(n), <br/> 0 ≤ j < j' ≤ r | ||
| + | | p(n) * r<sup>2</sup>/2 | ||
| + | |- | ||
| + | | rowspan="2" | ヘッド位置に関する制約 | ||
| + | | 時刻 i においてヘッドはいずれかのテープ位置にある | ||
| + | | { H [ t<sub>i</sub>, -p(n) ], H [ t<sub>i</sub>, -p(n)+1 ], ..., H [ t<sub>i</sub>, p(n)+1</sub> ] } | ||
| + | | 0 ≤ i ≤ p(n) | ||
| + | | p(n) | ||
| + | |- | ||
| + | | 時刻 i においてヘッドは二つの位置を同時に取らない | ||
| + | | { ￢H [ t<sub>i</sub>, j ], ￢H [ t<sub>i</sub>, j' ] } | ||
| + | | 0 ≤ i ≤ p(n), <br/> -p(n) ≤ j < j' ≤ p(n)+1 | ||
| + | | p(n) * 2 p(n)<sup>2</sup> | ||
| + | |- | ||
| + | | rowspan="2" | テープに書く記号に関する制約 | ||
| + | | 時刻 i においてテープ位置 j にはいずれかの記号 k がある | ||
| + | | { S [ t<sub>i</sub>, j, s<sub>0</sub> ], S [ t<sub>i</sub>, j, s<sub>1</sub> ], ..., S [ t<sub>i</sub>, j, s<sub>v</sub> ] } | ||
| + | | 0 ≤ i ≤ p(n), <br/> -p(n) ≤ j ≤ p(n)+1 | ||
| + | | p(n) * 2 p(n) | ||
| + | |- | ||
| + | | 時刻 i においてテープ位置 j は二種の記号を同時に取らない | ||
| + | | { ￢S [ t<sub>i</sub>, j, s<sub>k</sub> ], ￢S [ t<sub>i</sub>, j, s<sub>k'</sub> ] } | ||
| + | | 0 ≤ i ≤ p(n), <br/> -p(n) ≤ j ≤ p(n)+1, <br/> 0 ≤k < k' ≤ v | ||
| + | | p(n) * 2 p(n) * v | ||
| + | |- | ||
| + | | ''M'' の初期設定に関する制約 | ||
| + | | 初めはテープに入力 x = k<sub>1</sub>k<sub>2</sub>...k<sub>n</sub>のみ | ||
| + | | { Q [ t<sub>0</sub>, q<sub>0</sub> ] }, { H [ t<sub>0</sub>, 1 ] }, { S [ t<sub>0</sub>, 0, s<sub>0</sub> ] }, <br/> { S [ t<sub>0</sub>, 1, k<sub>1</sub> ] }, { S [ t<sub>0</sub>, 2, k<sub>2</sub> ] }, ... { S [ t<sub>0</sub>, n, k<sub>n</sub> ] }, <br/> { S [ t<sub>0</sub>, n+1, b ] }, { S [ t<sub>0</sub>, n+2, b ] }, ... { S [ t<sub>0</sub>, p(n)+1, b ] } | ||
| + | | p(n) | ||
| + | |- | ||
| + | | 受理状態に関する制約 | ||
| + | | 時刻 p(n) には ''M'' が状態 q<sub>Y</sub> に到達 | ||
| + | | { Q [ t<sub>p(n)</sub>, q<sub>Y</sub> ] } | ||
| + | | 1 | ||
| + | |- | ||
| + | | rowspan="2" | 状態遷移に関する制約 | ||
| + | | 時刻 i にテープ j をアクセスしなければ j の中身は i+1 に変化しない | ||
| + | | { ￢S [ t<sub>i</sub>, j, s<sub>l</sub> ], H [ t<sub>i</sub>, j ], S [ t<sub>i+1</sub>, j, s<sub>l</sub> ] } | ||
| + | | 0 ≤ i ≤ p(n), <br/> -p(n) ≤ j ≤ p(n)+1, <br/> 0 ≤ l ≤ v | ||
| + | | 2 p(n)<sup>2</sup> * v | ||
| + | |- | ||
| + | | 時刻 i に | ||
| + | |||
|} | |} | ||
Revision as of 11:53, 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, ￢u2, u3 } という節は、 u1 = F かつ u2 = T かつ u3 = 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 ≤ 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 ... 空白記号や入力記号も含めた、テープ記号数 | Γ |
これらの変数を用いて次表に示す節を作成し、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 に |
