Aritalab:Lecture/Algorithm/CooksTheorem - Revision history

Adm: /* SAT問題と3SAT問題 */

2011-10-13T23:58:52Z

‎SAT問題と3SAT問題

Adm: /* NP完全性のインパクト */

2011-10-12T15:50:39Z

‎NP完全性のインパクト

Adm: /* SAT問題と3-SAT問題 */

2011-10-12T15:33:13Z

‎SAT問題と3-SAT問題

Adm: /* SAT問題と3-SAT問題 */

2011-10-12T15:05:19Z

‎SAT問題と3-SAT問題

Adm: /* SAT問題と3-SAT問題 */

2011-10-12T15:02:34Z

‎SAT問題と3-SAT問題

Adm: /* SAT問題と3-SAT問題 */

2011-10-12T13:07:11Z

‎SAT問題と3-SAT問題

Adm: /* NP完全性のインパクト */

2011-10-07T05:37:47Z

‎NP完全性のインパクト

Adm: /* NP完全性のインパクト */

2011-10-07T05:35:01Z

‎NP完全性のインパクト

Adm: /* SAT問題と3-SAT問題 */

2011-10-06T05:01:26Z

‎SAT問題と3-SAT問題

Adm: /* SAT問題と3-SAT問題 */

2011-10-06T05:00:03Z

‎SAT問題と3-SAT問題

@@ Line 158: / Line 158: @@
 つまり、SAT問題の表現能力はチューリングマシンのあらゆる動作列、すなわちクラスNPに属する全ての問題を包含しているのです。そのため、どんなSAT問題を与えられても多項式時間で解くアルゴリズムがあるとするならば、クラス NP に属するいかなる問題でもO(p(n)<sup>4</sup>)時間でSAT問題に変換することで、それらを多項式時間で解くことになります。つまり、SAT問題は NP に属するどの問題と比較しても同等以上に難しい、NP完全であることが示されています。
-==SAT問題と3SAT問題==
+==SAT & 3SAT==
 SAT問題は複雑な論理式が多く使われており、解くのが十分に難しそうです。しかし、各節にリテラルをちょうど3つしか含まないように制約を設けた3-SATISFIABILITYもNP完全であることが簡単に示せます。

@@ Line 153: / Line 153: @@
 | 問題 x がクラスNPに属する ||&hArr; || 定義より、x に多項式時間でYESという NDTM のプログラムが存在
 |-
-| ||&hArr; || クックの定理により NDTM の入力とプログラムを多項式時間で変換したSAT問題が存在
+| ||&hArr; || クックの定理により NDTM の入力とプログラム（の可能な全動作列）を多項式時間で変換したSAT問題が存在
 |}
-つまり、SAT問題の表現能力はクラスNPに属する全ての問題を包含しているのです。そのため、どんなSAT問題を与えられても多項式時間で解くアルゴリズムがあるとするならば、クラス NP に属する全ての問題をO(p(n)<sup>4</sup>)時間でSAT問題に変換することで、それらを多項式時間で解くことになります。つまり、SAT問題は NP に属するどの問題と比較しても同等以上に難しい、NP完全であることが示されています。
+つまり、SAT問題の表現能力はチューリングマシンのあらゆる動作列、すなわちクラスNPに属する全ての問題を包含しているのです。そのため、どんなSAT問題を与えられても多項式時間で解くアルゴリズムがあるとするならば、クラス NP に属するいかなる問題でもO(p(n)<sup>4</sup>)時間でSAT問題に変換することで、それらを多項式時間で解くことになります。つまり、SAT問題は NP に属するどの問題と比較しても同等以上に難しい、NP完全であることが示されています。
 ==SAT問題と3SAT問題==

@@ Line 158: / Line 158: @@
 つまり、SAT問題の表現能力はクラスNPに属する全ての問題を包含しているのです。そのため、どんなSAT問題を与えられても多項式時間で解くアルゴリズムがあるとするならば、クラス NP に属する全ての問題をO(p(n)<sup>4</sup>)時間でSAT問題に変換することで、それらを多項式時間で解くことになります。つまり、SAT問題は NP に属するどの問題と比較しても同等以上に難しい、NP完全であることが示されています。
-==SAT問題と3-SAT問題==
+==SAT問題と3SAT問題==
 SAT問題は複雑な論理式が多く使われており、解くのが十分に難しそうです。しかし、各節にリテラルをちょうど3つしか含まないように制約を設けた3-SATISFIABILITYもNP完全であることが簡単に示せます。
-;3-SAT問題はNP完全
+;3SAT問題はNP完全
--SATを充足させる変数の T, F が与えられたらすぐにYESと判断できるため、3-SAT &isin; NP です。
+SATを充足させる変数の T, F が与えられたらすぐにYESと判断できるため、3SAT &isin; NP です。
-ここで SAT から 3-SAT への変換を考えます。SATにおける各節 C を以下のように変換します。
+ここで SAT から 3SAT への変換を考えます。SATにおける各節 C を以下のように変換します。
 * 変数を1個含む場合 C = { z }
@@ Line 185: / Line 185: @@
 逆に、置き換えた節 C' が充足可能である時は、必ず z<sub>1</sub> ... z<sub>k</sub> のいずれかが T にならざるを得ませんから（背理法ですぐに証明できます）、もとの節 C が充足可能になります。
-以上をまとめると、任意のSAT問題を与えられたら、節の数とほぼ同数の変数を追加に用意するだけで等価な 3-SAT 問題を構成できることが示せました。
+以上をまとめると、任意のSAT問題を与えられたら、節の数とほぼ同数の変数を追加に用意するだけで等価な 3SAT 問題を構成できることが示せました。
 このように問題を変換 (reduce) することで、[[Aritalab:Lecture/Algorithm/Reducibility|様々な問題がNP完全であることを証明]]できます。重要な組み合わせ問題に対してこれをCookの定理の翌年に示したのが、現在はバイオインフォマティクスを研究している Richard M Karp でした。

← Older revision		Revision as of 15:05, 12 October 2011
Line 186:		Line 186:

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

@@ Line 162: / Line 162: @@
 SAT問題は複雑な論理式が多く使われており、解くのが十分に難しそうです。しかし、各節にリテラルをちょうど3つしか含まないように制約を設けた3-SATISFIABILITYもNP完全であることが簡単に示せます。
-;定理：3-SAT問題はNP完全である
+;3-SAT問題はNP完全
 -SATを充足させる変数の T, F が与えられたらすぐにYESと判断できるため、3-SAT &isin; NP です。

← Older revision		Revision as of 13:07, 12 October 2011
Line 186:		Line 186:

	以上をまとめると、任意のSAT問題を与えられたら、節の数とほぼ同数の変数を追加に用意するだけで等価な 3-SAT 問題を構成できることが示せました。		以上をまとめると、任意のSAT問題を与えられたら、節の数とほぼ同数の変数を追加に用意するだけで等価な 3-SAT 問題を構成できることが示せました。
		+	このように問題を変換 (reduce) できることを用いて、[[Aritalab:Lecture/Algorithm/Reducibility\|様々な問題がNP完全であることを証明]]できます。

@@ Line 177: / Line 177: @@
 * 変数を k (> 3) 個含む場合 C = { z<sub>1</sub>, z<sub>2</sub>, ... z<sub>k</sub> }
 : C にしか使わない変数を k&minus;3 個用意し { x<sub>1</sub>, x<sub>2</sub>, ... x<sub>k-3</sub> } 、次の k&minus;2 節で置き換えます。
-: { { z<sub>1</sub>, z<sub>2</sub>, x<sub>1</sub> } &and; { &not;x<sub>1</sub>, z<sub>3</sub>, x<sub>2</sub> } &and; { &not;x<sub>2</sub>, z<sub>4</sub>, x<sub>3</sub> } } ... &and; { &not;x<sub>k-3</sub>, z<sub>k-1</sub>, z<sub>k</sub> } }
+: C' = { { z<sub>1</sub>, z<sub>2</sub>, x<sub>1</sub> } &and; { &not;x<sub>1</sub>, z<sub>3</sub>, x<sub>2</sub> } &and; { &not;x<sub>2</sub>, z<sub>4</sub>, x<sub>3</sub> } } ... &and; { &not;x<sub>k-3</sub>, z<sub>k-1</sub>, z<sub>k</sub> } }
 もとの節に含まれる変数の数が 3 個以下の場合、上記の変換において、もとの節における変数のアサインメントで充足可能 &hArr; 置き換えた節が充足可能　であることがすぐにわかります。 新しく導入する変数のアサインメントは T でも F でもよいからです。変数を k 個含むときだけ少し面倒です。
-もとの節　C = { z<sub>1</sub>, z<sub>2</sub>, ... z<sub>k</sub> } が充足可能な時、少なくともある変数 z<sub>m</sub> が T になっています。もし m が 1 か 2 の場合は x<sub>1</sub> ... x<sub>k-3</sub> を全て F にすれば、変換後の節が充足されます。もし m が k&minus;1 か k の場合は、x<sub>1</sub> ... x<sub>k-3</sub> を全て T にすれば変換後の節が充足されます。もし m が l の場合は、 x<sub>1</sub> ... x<sub>l-2</sub> をすべて T にし、 x<sub>l-1</sub> ... x<sub>k-3</sub> を全て F にすれば充足されます。 T となるリテラルが1個以上の場合は T の数が増えるだけです。逆に、置き換えた節が充足可能である時、必ず z<sub>1</sub> ... z<sub>k</sub> のいずれかが T にならざるを得ませんから（背理法ですぐに証明できます）、もとの節が充足可能です。
+もとの節　C = { z<sub>1</sub>, z<sub>2</sub>, ... z<sub>k</sub> } が充足可能な時、少なくともある変数 z<sub>m</sub> が T になっています。もし m が 1 か 2 の場合は x<sub>1</sub> ... x<sub>k-3</sub> を全て F にすれば、変換後の節 C' が充足されます。もし m が k&minus;1 か k の場合は、x<sub>1</sub> ... x<sub>k-3</sub> を全て T にすれば節 C' が充足されます。もし m が l の場合は、 x<sub>1</sub> ... x<sub>l-2</sub> をすべて T にし、 x<sub>l-1</sub> ... x<sub>k-3</sub> を全て F にすれば C' が充足されます。 T となるリテラルが1個以上の場合は T の数が増えるだけなので、C' の充足性に変化はありません。
 以上をまとめると、任意のSAT問題を与えられたら、節の数とほぼ同数の変数を追加に用意するだけで等価な 3-SAT 問題を構成できることが示せました。