Aritalab:Lecture/Algorithm/Reducibility
問題の変換
SAT問題がNP完全であることが証明されれば、他のNP完全問題をみつけることは楽になります。 ある問題がNP完全であることを示すには
- クラス NP に属する
- その問題がNP完全の問題を部分問題として含んでいる
ことを示せばよいだけです。
三次元マッチング
三次元マッチング (3-dimensional matching; 3DM) は、マッチング問題（または結婚問題）と呼ばれる有名な組み合わせ問題の三次元版です。
問題: サイズのひとしい集合 W, X, Y から一つずつ要素を取り出して作った三つ組の集合 M ⊆ W × X × Y が与えられた時、Mの中から |W| 組を取り出して、W, X, Y のいずれの要素も取りこぼしや重複なく選ぶことができるか。
例: W = { A, B, C }; X = { a, b, c }; Y = { 1, 2, 3 };
- M = (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問題は変数 { u1, u2, ... , un } を用いた節集合 C = { c1, c2, ... , cm } で構成されるとします。
三つ組の集合 M は、真偽値の設定用、充足性判定用、ガーベッジコレクション用の 3 タイプ用意します。
- 真偽値の設定用
3SATに登場する各変数 u に対し、節の数 m 個に対応する以下のマッチングモジュールを用意します。
TT = { (¬u[k], a[k], b[k]): 1 ≤ k ≤ m }
TF = { (u[k], a[k+1], b[k]): 1 ≤ k < m } ∪ { u[m], a[1], b[m] }
ここで変数 a, b は変数 u を3DMに変換するために用いるもので、各 u の変換にしか登場しません。 このユニットをみたすマッチングは、TT に対応する m 個の三つ組を選択するか、TF に対応する m 個を選択するかしかありません。つまり、変数 u を T か F のどちらかに設定できます。3SATを充足するアサインメントで変数 u が T のとき、TT の三つ組 ( m 個) を選択します。変数 u が F のときは TF を選択します。
- 充足性判定用
充足性判定用のマッチングモジュールは、m 個ある各節 c 毎に用意します。節 c に出てくる変数が (ui, uj, uk) だとすると
{ ui, s1, s2 } ∪ { uj, s1, s2 } ∪ { uk, s1, s2 }
を用意します。（もし節の中で ¬ui という使われ方をしていたら、{ ¬ui, s1, s2 } という組をつくります。）ここでs1, s2は変換用の変数で、節 c を特定するために用います。各節を充足するには T となる要素が必ず一つは存在するので、その要素が s1, s2 とマッチングするように三つ組を選びます。
- ガーベッジコレクション用
充足性判定の部分では、各節において一つだけ T とする変数を選んでおり、残りを使いません。充足に使われなかった残りのリテラルは、ガーベッジコレクション用の三つ組で利用します。 ガーベッジコレクションの三つ組は専用の変数 g1, g2 を用いて
{ (u[j], g1[k], g2[k]), (¬u[j], g1[k], g2[k]): 1 ≤ j ≤ m, 1 ≤ k ≤ m(n−1) }
と定義します。3SATに出現する変数に対応する真偽値設定用の要素は 2nm 個あります。そのうち、真偽値設定モジュールで半数を利用するので、残りは nm 個です。そのうち、充足性判定用に各節から 1 つずつ、合計 m 個の要素を使います。残った m(n−1) 個をガーベッジコレクションするので、 g1[k], g2[k]を 1 ≤ k ≤ m(n−1) 個用意し、それぞれについて、nm 個あるどの変数でもガーベッジコレクトできるようにします。
- 例
3SAT 問題 (x ∨ y ∨ z) ∧ (¬ x ∨ ¬y ∨ z) を変換します。変数は x, y, z 、節の数は2つなので以下の真偽値設定モジュールを用意します。赤く示してあるのは、¬x, y, z を T に設定した時に選択する三つ組です。
| 変数 x: | (x[1], b[1], a[2]) | (¬x[1], a[1], b[1]) | (x[2], b[2], a[1]) | (¬x[2], a[2], b[2]) |
| 変数 y: | (¬y[1], c[1], d[1]) | (y[1], d[1], c[2]) | (¬y[2], c[2], d[2]) | (y[2], d[2], c[1]) |
| 変数 z: | (¬z[1], e[1], f[1]) | (z[1], f[1], e[2]) | (¬z[2], e[2], f[2]) | (z[2], f[2], e[1]) |
また二つの節に対応する充足判定モジュールを用意します。ここでは ¬x, y を T とするので赤字で示した三つ組を選択します。（他の選択方法もあります。）
| 節1: | (x[1], s1, s2) | (y[1], s1, s2) | (z[1], s1, s2) |
| 節2: | (¬x[2], t1, t2) | (y[2], t1, t2) | (z[2], t1, t2) |
最後に、節を T にするのに利用しなかった要素 x[1], y[2], z[1], z[2] がマッチングから外れているのでこれらをガーベッジコレクションします。
| g[1]: | (x[1], g1[1], g2[1]) | (¬x[1], g1[1], g2[1]) | (x[2], g1[1], g2[1]) | (¬x[2], g1[1], g2[1]) |
|---|---|---|---|---|
| (y[1], g1[1], g2[1]) | (¬y[1], g1[1], g2[1]) | (y[2], g1[1], g2[1]) | (¬y[2], g1[1], g2[1]) | |
| (z[1], g1[1], g2[1]) | (¬z[1], g1[1], g2[1]) | (z[2], g1[1], g2[1]) | (¬z[2], g1[1], g2[1]) | |
| g[2]: | (x[1], g1[2], g2[2]) | (¬x[1], g1[2], g2[2]) | (x[2], g1[2], g2[2]) | (¬x[2], g1[2], g2[2]) |
| (y[1], g1[2], g2[2]) | (¬y[1], g1[2], g2[2]) | (y[2], g1[2], g2[2]) | (¬y[2], g1[2], g2[2]) | |
| (z[1], g1[2], g2[2]) | (¬z[1], g1[2], g2[2]) | (z[2], g1[2], g2[2]) | (¬z[2], g1[2], g2[2]) | |
| g[3]: | (x[1], g1[3], g2[3]) | (¬x[1], g1[3], g2[3]) | (x[2], g1[3], g2[3]) | (¬x[2], g1[3], g2[3]) |
| (y[1], g1[3], g2[3]) | (¬y[1], g1[3], g2[3]) | (y[2], g1[3], g2[3]) | (¬y[2], g1[3], g2[3]) | |
| (z[1], g1[3], g2[3]) | (¬z[1], g1[3], g2[3]) | (z[2], g1[3], g2[3]) | (¬z[2], g1[3], g2[3]) | |
| g[m(n−1)] | (x[1], g1[4], g2[4]) | (¬x[1], g1[4], g2[4]) | (x[2], g1[4], g2[4]) | (¬x[2], g1[4], g2[4]) |
| (y[1], g1[4], g2[4]) | (¬y[1], g1[4], g2[4]) | (y[2], g1[4], g2[4]) | (¬y[2], g1[4], g2[4]) | |
| (z[1], g1[4], g2[4]) | (¬z[1], g1[4], g2[4]) | (z[2], g1[4], g2[4]) | (¬z[2], g1[4], g2[4]) |
まとめると、m 節 n 変数の 3SAT 問題は、2mn + 3m + 2mn × m(n−1) 組からなる 3DM 問題に変換されることがわかります。 3SAT を充足可能とする変数のアサインメントに従えば 3DM の解を構成でき、逆に 3DM の解となる三つ組を選択すると、 3SAT を充足します。
