Aritalab:Lecture/Algorithm/Reducibility - Revision history

Adm at 01:49, 18 October 2011

2011-10-18T01:49:02Z

Adm: /* 3DM: Three Dimensional Matching */

2011-10-14T00:01:33Z

‎3DM: Three Dimensional Matching

Adm: /* 問題の変換 */

2011-10-12T18:46:06Z

‎問題の変換

Adm: /* 問題の変換 */

2011-10-12T16:13:59Z

‎問題の変換

Adm: /* Set Cover */

2011-10-12T16:13:04Z

‎Set Cover

Adm: /* Set Cover */

2011-10-12T16:12:00Z

‎Set Cover

Adm: /* Partition */

2011-10-12T16:06:52Z

‎Partition

Adm at 14:38, 12 October 2011

2011-10-12T14:38:09Z

Adm: /* 3DM: Three Dimensional Matching */

2011-10-12T14:29:32Z

‎3DM: Three Dimensional Matching

Adm: /* 3DM: Three Dimensional Matching */

2011-10-12T14:29:09Z

‎3DM: Three Dimensional Matching

@@ Line 6: / Line 6: @@
 ことを示せばよいだけです。
-ここでは、3SAT &rarr; 3DM &rarr; Partition, Exact Cover という順番でNP完全問題を紹介します。この順番は 1972 年に
+ここでは、3SAT &rarr; 3DM &rarr; Partition, Exact Cover, 3SAT &rarr; Vertex Cover &rarr; Hamiltonian Circuit という順番でNP完全問題を紹介します。この順番は 1972 年に
-Richard M Karp が 21 個のNP完全問題を変換した論文 "Reducibility Among Combinatorial Problems" (In RE Miller and JW Thatcher (eds) Complexity of Computer Computations. Plenum (New York) pp. 85–103 に基づいています。次のページでは[[Aritalab:Lecture/Algorithm/Reducibility2|3SAT &rarr; Vertex Cover &rarr; Hamiltonian Circuit]] を示します。
+Richard M Karp が 21 個のNP完全問題を変換した論文 "Reducibility Among Combinatorial Problems" (In RE Miller and JW Thatcher (eds) Complexity of Computer Computations. Plenum (New York) pp. 85–103 に基づいています。
 Garey & Johnson の教科書も参考にしてください。
@@ Line 202: / Line 202: @@
 集合被覆問題 SC において、各要素の出現回数を 1 回に限った場合が EC になっています。そのため SC も NP 完全です。

@@ Line 11: / Line 11: @@
 Garey & Johnson の教科書も参考にしてください。
-==3DM: Three Dimensional Matching==
+==Three Dimensional Matching (3DM)==
 三次元マッチング (3-dimensional matching; 3DM) は、マッチング問題（または結婚問題）と呼ばれる有名な組み合わせ問題の三次元版です。

@@ Line 7: / Line 7: @@
 ここでは、3SAT &rarr; 3DM &rarr; Partition, Exact Cover という順番でNP完全問題を紹介します。この順番は 1972 年に
-Richard M Karp が 21 個のNP完全問題を変換した論文 "Reducibility Among Combinatorial Problems" (In RE Miller and JW Thatcher (eds) Complexity of Computer Computations. Plenum (New York) pp. 85–103 に基づいています。Garey & Johnson の教科書も参考にしてください。
+Richard M Karp が 21 個のNP完全問題を変換した論文 "Reducibility Among Combinatorial Problems" (In RE Miller and JW Thatcher (eds) Complexity of Computer Computations. Plenum (New York) pp. 85–103 に基づいています。次のページでは[[Aritalab:Lecture/Algorithm/Reducibility2|3SAT &rarr; Vertex Cover &rarr; Hamiltonian Circuit]] を示します。
 ==3DM: Three Dimensional Matching==

@@ Line 6: / Line 6: @@
 ことを示せばよいだけです。
-ここでは、3SAT &rarr; 3DM &rarr; Partition という順番で二つのNP完全問題を紹介します。この順番は 1972 年に
+ここでは、3SAT &rarr; 3DM &rarr; Partition, Exact Cover という順番でNP完全問題を紹介します。この順番は 1972 年に
 Richard M Karp が 21 個のNP完全問題を変換した論文 "Reducibility Among Combinatorial Problems" (In RE Miller and JW Thatcher (eds) Complexity of Computer Computations. Plenum (New York) pp. 85–103 に基づいています。Garey & Johnson の教科書も参考にしてください。

@@ Line 194: / Line 194: @@
 : 集合 X と、X の部分集合の集合 C に対し、部分集合 C' &sub; C で X の全ての要素がちょうど 1 回だけ現れるものがあるか。
-EC において部分集合の大きさを 3 に限定した場合が X3C になっています。そのため EC も NP 完全です。Exact Cover は Hitting Set と呼ばれる問題と等価であり、ここから [[Aritalab:Lecture/Algorithm/Sudoku|数独 (Sudoku) 問題の NP 完全性]]が示せます。
+EC において部分集合の大きさを 3 に限定した場合が X3C になっています。そのため EC も NP 完全です。Exact Cover は Hitting Set と呼ばれる問題と等価であり、ここから [[Aritalab:Lecture/Algorithm/Sudoku|数独 (Sudoku) 問題の NP 完全性]]が示せます。さらに問題を一般化しましょう。
 ;Set Cover (SC)
 : 集合 X と、X の部分集合の集合 C に対し、部分集合 C' &sub; C で X の全ての要素が 1 回以上現れるものがあるか。
-SC において、各要素の出現回数を 1 回に限った場合が EC になっています。そのため SC も NP 完全です。
+集合被覆問題 SC において、各要素の出現回数を 1 回に限った場合が EC になっています。そのため SC も NP 完全です。

@@ Line 189: / Line 189: @@
 :サイズが 3q の集合 X と、X の要素の三つ組の集合 C に対し、部分集合 C' &sub; C で X の全ての要素がちょうど 1 回だけ現れるものがあるか。
-X3Cにおいて、集合 X を 3つ W &cup; X &cup; Y に分けた場合が 3DM になっています。つまりX3Cの部分問題が 3DM になるので X3C は NP 完全です。さらに問題を一般化しましょう。
+X3Cにおいて、集合 X を 3つ (W &cup; X &cup; Y) に分けて各集合から 1 つずつ選ぶように制限した場合が 3DM になっています。つまりX3Cの部分問題が 3DM になるので X3C は NP 完全です。さらに問題を一般化しましょう。
 ;Exact Cover (EC)

← Older revision		Revision as of 16:06, 12 October 2011
Line 182:		Line 182:

	でありマッチング (A, b, 1) (B, a, 3) (C, c, 2) に相当します。		でありマッチング (A, b, 1) (B, a, 3) (C, c, 2) に相当します。
		+
		+	==Set Cover==
		+	3DM は集合の被覆問題と考えることができます。以下の Exact Cover by 3-Sets (X3C) 問題は、3DM 問題を一般化した形になっています。
		+
		+	;X3C
		+	:サイズが 3q の集合 X と、X の要素の三つ組の集合 C に対し、部分集合 C' ⊂ C で X の全ての要素がちょうど 1 回だけ現れるものがあるか。
		+
		+	X3Cにおいて、集合 X を 3つ W ∪ X ∪ Y に分けた場合が 3DM になっています。つまりX3Cの部分問題が 3DM になるので X3C は NP 完全です。さらに問題を一般化しましょう。
		+
		+	;Exact Cover (EC)
		+	: 集合 X と、X の部分集合の集合 C に対し、部分集合 C' ⊂ C で X の全ての要素がちょうど 1 回だけ現れるものがあるか。
		+
		+	EC において部分集合の大きさを 3 に限定した場合が X3C になっています。そのため EC も NP 完全です。Exact Cover は Hitting Set と呼ばれる問題と等価であり、ここから [[Aritalab:Lecture/Algorithm/Sudoku\|数独 (Sudoku) 問題の NP 完全性]]が示せます。
		+
		+	;Set Cover (SC)
		+	: 集合 X と、X の部分集合の集合 C に対し、部分集合 C' ⊂ C で X の全ての要素が 1 回以上現れるものがあるか。
		+
		+	SC において、各要素の出現回数を 1 回に限った場合が EC になっています。そのため SC も NP 完全です。

@@ Line 130: / Line 130: @@
 SAT を充足可能とする変数のアサインメントに従えば 3DM の解を構成でき、逆に 3DM の解となる三つ組を選択すると、 3SAT を充足します。
-==PARTITION==
+==Partition==
 二分割 (partition) 問題は以下のように定義されます。
@@ Line 150: / Line 150: @@
 まとめると、W, X, Y のサイズが q、三つ組が k 個ある 3DM 問題が与えられたら、(k+1)進数で表現した 3q 桁の数字 k + 2 個を用いた二分割問題に変換することができました。
-===3DM &rarr; PARTITION の例===
+===3DM &rarr; Partition の例===
-例として以下の問題をPARTITIONに変換しましょう。
+例として以下の 3DM 問題を二分割問題に変換しましょう。
 : W = { A, B, C }; X = { a, b, c }; Y = { 1, 2, 3 };
 : E = (A, b, 1), (A, a, 3), (B, a, 1), (B, a, 3), (B, b, 1), (B, c, 2), (C, c, 2)

← Older revision		Revision as of 14:29, 12 October 2011
Line 21:		Line 21:


−	;~~定理：3DM~~ はNP完全	+	;3DM はNP完全

	正解となる組を与えられたら、集合 W, X, Y の要素が全て重複なく使われているかどうかはすぐに判定できるので 3DM ∈ NP です。		正解となる組を与えられたら、集合 W, X, Y の要素が全て重複なく使われているかどうかはすぐに判定できるので 3DM ∈ NP です。