Aritalab:Lecture/Algorithm/Reducibility

Revision as of 14:03, 6 October 2011

問題の変換

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

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

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

三次元マッチング

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

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

定理：3DM はNP完全問題

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

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

• 真偽値の設定用

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

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

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

ここで変数 a, b は変数 u を3DMに変換するために用いるもので、各 u の変換にしか登場しません。 このユニットをみたすマッチングは、T^T に対応する m 個の三つ組を選択するか、T^F に対応する m 個を選択するかしかありません。つまり、変数 u を T か F のどちらかに設定でき、この割り当てが全ての節において等しいことを保証します。

• 充足性判定用

充足性判定用のマッチングモジュールは、m 個ある各節 c 毎に用意します。節 c に出てくるリテラル u_i それぞれについて

{ u_i, s₁, s₂ } ∪ { ¬u_i, s₁, s₂ }

を用意します。ここでs₁, s₂は変換用の変数で、各節 c 毎に用意します。マッチングは u_i か ¬u_i のどちらかしか選択できません。どちらかを選ぶ作業が、節 c を変数 u によって充足する作業に相当します。

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

充足に使われなかった残りのリテラルは、ガーベッジコレクション用の三つ組で解消します。 ガーベッジコレクションの三つ組みは専用の変数 g₁, g₂ を用いて

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

と定義します。もし変数 u のアサインメントが T で、ある節 c を充足するのに使われると仮定します。