Aritalab:Lecture/Algorithm/Reducibility

Revision as of 01:13, 13 October 2011

問題の変換

SAT問題がNP完全であることが証明されれば、他のNP完全問題をみつけることは楽になります。 ある問題がNP完全であることを示すには

• クラス NP に属する
• その問題がNP完全の問題を部分問題として含んでいる

ことを示せばよいだけです。

ここでは、3SAT → 3DM → 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 の教科書も参考にしてください。

3DM: Three Dimensional Matching

三次元マッチング (3-dimensional matching; 3DM) は、マッチング問題（または結婚問題）と呼ばれる有名な組み合わせ問題の三次元版です。

問題: サイズのひとしい集合 W, X, Y から一つずつ要素を取り出して作った三つ組の集合 E ⊆ W × X × Y が与えられた時、Eの中から |W| 組を取り出して、W, X, Y のいずれの要素も取りこぼしや重複なく選ぶことができるか。

例: W = { A, B, C }; X = { a, b, c }; Y = { 1, 2, 3 };

E = (A, a, 1), (A, a, 3), (B, a, 1), (B, a, 3), (B, b, 1), (B, c, 2), (C, c, 2)

この問題の解は (A, b, 1) (B, a, 3) (C, c, 2) で、W, X, Y の要素がそれぞれ1度ずつ使われています。

3DM はNP完全

正解となる組を与えられたら、集合 W, X, Y の要素が全て重複なく使われているかどうかはすぐに判定できるので 3DM ∈ NP です。 これから 3SAT問題を3DM問題に変換しましょう。3SAT問題は変数 { u₁, u₂, ... , u_n } を用いた節集合 C = { c₁, c₂, ... , c_m } で構成されるとします。

三つ組の集合 M は、真偽値の設定用、充足性判定用、ガーベッジコレクション用の 3 タイプ用意します。

• 真偽値の設定用

3SATに登場する各変数 u に対し、節の数 m 個に対応する以下のマッチングモジュール M を用意します。

M_u^T = { (¬u[k], a[k], b[k]): 1 ≤ k ≤ m }

M_u^F = { (u[k], a[k+1], b[k]): 1 ≤ k < m } ∪ { u[m], a[1], b[m] }

ここで変数 a, b は変数 u を3DMに変換するために用いるもので、各 u の変換にしか登場しません。 このユニットをみたすマッチングは、M^T に対応する m 個の三つ組を選択するか、M^F に対応する m 個を選択するかしかありません。つまり、変数 u を T か F のどちらかに設定できます。3SATを充足するアサインメントで変数 u が T のとき、M^T の三つ組 ( m 個) を選択します。変数 u が F のときは M^F を選択します。

• 充足性判定用

充足性判定用のマッチングモジュールは、m 個ある各節 c 毎に用意します。節 c に出てくる変数が (u_i, u_j, u_k) だとすると

M_c: { u_i, s₁, s₂ } ∪ { u_j, s₁, s₂ } ∪ { u_k, s₁, s₂ }

を用意します。（もし節の中で ¬u_i という使われ方をしていたら、{ ¬u_i, s₁, s₂ } という組をつくります。）ここでs₁, s₂は変換用の変数で、節 c を特定するために用います。各節を充足するには T となる要素が必ず一つは存在するので、その要素が s₁, s₂ とマッチングするように三つ組を選びます。

• ガーベッジコレクション用

充足性判定の部分では、各節において一つだけ T とする変数を選んでおり、残りを使いません。充足に使われなかった残りのリテラルは、ガーベッジコレクション用の三つ組で利用します。 ガーベッジコレクションの三つ組は専用の変数 g₁, g₂ を用いて

G_k: { (u[j], g₁[k], g₂[k]), (¬u[j], g₁[k], g₂[k]): 1 ≤ j ≤ m, 1 ≤ k ≤ m(n−1) }

と定義します。3SATに出現する変数に対応する真偽値設定用の要素は 2nm 個あります。そのうち、真偽値設定モジュールで半数を利用するので、残りは nm 個です。そのうち、充足性判定用に各節から 1 つずつ、合計 m 個の要素を使います。残った m(n−1) 個をガーベッジコレクションするので、 g₁[k], g₂[k]を 1 ≤ k ≤ m(n−1) 個用意し、それぞれについて、nm 個あるどの変数でもガーベッジコレクトできるようにします。

3SAT→3DMの例

3SAT 問題 (x ∨ y ∨ z) ∧ (¬ x ∨ ¬y ∨ z) を変換します。変数は x, y, z 、節の数は2つなので以下の真偽値設定モジュールを用意します。赤く示してあるのは、¬x, y, z を T に設定する時に選択する三つ組で、それぞれ M_x^F, M_y^T, M_z^T に対応します。

また二つの節に対応する充足判定モジュールを用意します。ここでは ¬x, y を T とするので赤字で示した三つ組を選択します。（他の選択方法もあります。）

最後に、節を T にするのに利用しなかった要素 x[1], y[2], z[1], z[2] がマッチングから外れているのでこれらをガーベッジコレクションします。

まとめると、m 節　n 変数の 3SAT 問題は、2mn + 3m + 2mn × m(n−1) 組からなる 3DM 問題に変換されることがわかります。 3SAT を充足可能とする変数のアサインメントに従えば 3DM の解を構成でき、逆に 3DM の解となる三つ組を選択すると、 3SAT を充足します。

Partition

二分割 (partition) 問題は以下のように定義されます。

集合 A の各要素 a ∈ A に重さ s(a) ∈ Z⁺ が定義されているとき、総重量がちょうど半分になる A の部分集合 A' ⊂ A が存在するか。

集合 A の要素の総和 が奇数だったら直ちに NO と言えますし、重さ順に並べてバランスをとればうまく解けそうな問題に見えますが、これから二分割問題で 3DM 問題を表現できる（部分問題として含む）ことを示します。

二分割問題はNP完全

W, X, Y のサイズが q, 三つ組の集合 E が要素を k 個含む 3DM 問題を考えます。まず E に含まれる各要素を 3q 桁からなる数字で表現します。要素を e = { w_h, x_i, y_j } (1 ≤ h, i, j ≤ q) と書くと、この三つ組 e に対応する数字 f(e) は初めの q 桁のうち h 番目だけ 1 にして残りを 0、真ん中の q 桁のうち i 番目だけ 1 にして残りを 0、最後の q 桁のうち j 番目だけ 1 にして残りを 0 にしたものです。E の部分集合で 3DM を作れる場合、マッチングに対応する要素の数字を全部足し合わせた数は、3q 桁全てを 1 にした数に等しくなります。この、全桁が 1 である数を B とおきましょう。また全数字の和を とおきます。

二分割問題で用いる集合は、E に含まれる各要素 e を数字に変換した f(e) の値 k 個と、f₁ = 2F - B, f₂ = F + B からなる k + 2 個で構成します。これらの数字を全て足し合わせた値は ですから、E の部分集合を選んでちょうど二分割できた場合、その総和は 2F です。このとき、f₁, f₂ の両方を含むことはできず、どちらか片方のみ含みます。そのとき、f₁ または f₂ 以外の要素の和はちょうど B になり、 3DM を構成しています。

二分割問題は明らかにNPに属しています。数字への変換手続きは 3DM の問題サイズに比例する時間で可能です。また E の大きさが k の場合、例えば W の要素 w_i が最大 k 回現れる可能性があるため、数字に変換するときに (k+1) 進数を用います。そうすると総和である F を計算するときに桁の繰り上げが起きないので要素間で個数が影響することがありません。

まとめると、W, X, Y のサイズが q、三つ組が k 個ある 3DM 問題が与えられたら、(k+1)進数で表現した 3q 桁の数字 k + 2 個を用いた二分割問題に変換することができました。

3DM → 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)

W, X, Y のサイズが 3 なので 3 × 3 = 9 桁の数に変換します。

二分割問題は上の表にある 7 つの数に加えて、2F - 111 111 111 = 371 533 533 と、F + 111111111 = 352 433 433 の二つを加えた 9 つで構成されます。分割の解は

100 010 100 + 010 100 001 + 001 001 010 + 371 533 533 = 100 100 001 + 010 100 100 + 010 010 100 + 010 001 010 + 352 433 433

でありマッチング (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) に分けて各集合から 1 つずつ選ぶように制限した場合が 3DM になっています。つまりX3Cの部分問題が 3DM になるので X3C は NP 完全です。さらに問題を一般化しましょう。

Exact Cover (EC)

集合 X と、X の部分集合の集合 C に対し、部分集合 C' ⊂ C で X の全ての要素がちょうど 1 回だけ現れるものがあるか。

EC において部分集合の大きさを 3 に限定した場合が X3C になっています。そのため EC も NP 完全です。Exact Cover は Hitting Set と呼ばれる問題と等価であり、ここから 数独 (Sudoku) 問題の NP 完全性が示せます。さらに問題を一般化しましょう。

Set Cover (SC)

集合 X と、X の部分集合の集合 C に対し、部分集合 C' ⊂ C で X の全ての要素が 1 回以上現れるものがあるか。

集合被覆問題 SC において、各要素の出現回数を 1 回に限った場合が EC になっています。そのため SC も NP 完全です。