完全3次元マッチング問題 (3DM) のNP完全性証明

<script type="text/javascript" async src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.7/MathJax.js?config=TeX-MML-AM_CHTML">
</script>

# 3次元マッチング問題のNP完全性証明

## はじめに

この記事では、完全3次元マッチング問題（3DM）がNP完全であることの証明を詳しく解説します。証明は3SATからの多項式時間還元 (Karp還元) により行います。

> この記事は、Garey & Johnson著「Computers and Intractability: A Guide to the Theory of NP-Completeness」（1979）で示されている3次元マッチング問題のNP完全性証明について、その行間を補完する形で詳細な解説を試みたものです。証明の再構成にあたって細心の注意を払っていますが、正確性は保証できません。このため、研究や論文での引用には原著を参照することを強くお勧めします。

## 問題の定義

### 完全3次元マッチング問題（3DM）とは

完全3次元マッチング問題は以下のように定義されます:

**入力**: 
- 等しい濃度を持つ3つの集合 $A, B, C$
- $A \times B \times C$ の部分集合 $M$

**問題**:
$M$ の中から互いに素な部分集合を選び、$A, B, C$ の全ての要素を網羅できるかを判定する。

### 3SATとは

3SAT問題は以下のように定式化されます:

- $n$個の変数 $x_1, x_2, \ldots, x_n \in U$
- $m$個の節 $c_1, c_2, \ldots, c_m$ からなる論理式 $F$
- 各節は高々3つのリテラルの選言（OR）
- この論理式が充足可能かどうかを判定する

## NP完全性の証明

証明は以下の2ステップで行います:

1. $3DM \in NP$ の証明
2. $3SAT \leq_m 3DM$ の証明（多項式時間還元）

### Step 1: 3DM ∈ NP の証明

入力されたマッチングが完全3次元マッチングになっているかどうかの検証は、以下の手順で多項式時間で行えます:

- マッチングの要素が互いに素であることの確認
- すべての要素がカバーされていることの確認

### Step 2: 3SAT から 3DM への還元

以下の手順で3SATインスタンスを3DMインスタンスに変換します。

#### 1. 基本構成要素の定義

まず、変数の真偽値割り当てを表現するためのマッチングを定義します:

$T_i^t = \{(\bar{x}_i[j], a_i[j], b_i[j]) \mid 1 \leq j \leq m\}$  // $x_i$がTrueの場合

$T_i^f = \{(x_i[j], a_i[j+1], b_i[j]) \mid 1 \leq j < m\} \cup \{(x_i[m], a_i[1], b_i[m])\}$  // $x_i$がFalseの場合

ここで、$a_i \in Y, b_i \in Z$ は真偽値割り当ての制御に使用する補助要素です。

#### 2. 節に対応するマッチングの定義

各節$c_j$に対して以下のマッチングを定義します:

$C_j = \{(x_i[j], s_1[j], s_2[j]) \mid x_i \in c_j\} \cup \{(\bar{x}_i[j], s_1[j], s_2[j]) \mid \bar{x}_i \in c_j\}$

$s_1 \in Y, s_2 \in Z$ は節の真偽値割り当ての制御に使用する補助要素です。

#### 3. バランス調整用のマッチング

要素数を調整するためのダミーマッチング$G$を以下のように定義します:

$G = \{(x_i[j], g_1[k], g_2[k]), (\bar{x}_i[j], g_1[k], g_2[k]) \mid 1 \leq k \leq m(n-1), 1 \leq i \leq n, 1 \leq j \leq m\}$

#### 4. 最終的な集合の構成

これらを用いて、以下のように集合$X, Y, Z$とマッチングセットを構成します:

$X = \{x_i[j], \bar{x}_i[j] \mid 1 \leq i \leq n, 1 \leq j \leq m\}$
$Y = A \cup S_1 \cup G_1$
$Z = B \cup S_2 \cup G_2$

ここで:
$A = \{a_i[j] \mid 1 \leq i \leq n, 1 \leq j \leq m\}$
$B = \{b_i[j] \mid 1 \leq i \leq n, 1 \leq j \leq m\}$
$S_1 = \{s_1[j] \mid 1 \leq j \leq m\}$
$S_2 = \{s_2[j] \mid 1 \leq j \leq m\}$
$G_1 = \{g_1[k] \mid 1 \leq k \leq m(n-1)\}$
$G_2 = \{g_2[k] \mid 1 \leq k \leq m(n-1)\}$

$M = (\bigcup_{i=1}^n T_i) \cup (\bigcup_{j=1}^m C_j) \cup G$

### 還元の正当性

#### 1. 集合の濃度が等しいことの確認

構成した集合$X, Y, Z$の濃度は以下のようになります:

- $|X| = 2nm$
- $|Y| = |A| + |S_1| + |G_1| = nm + m + m(n-1) = 2nm$
- $|Z| = |B| + |S_2| + |G_2| = nm + m + m(n-1) = 2nm$

したがって、$|X| = |Y| = |Z| = 2nm$ となり、3つの集合の濃度は等しくなります。

#### 2. 多項式時間での変換可能性

各集合のサイズは変数の数$n$と節の数$m$の多項式で表現されるため、この変換は多項式時間で実行可能です。

#### 3. 充足可能性の保存（⇒方向）

3SATインスタンスが充足可能である場合、以下のように完全3次元マッチング$M'$を構成できます:

$M' = (\bigcup_{t(x_i)=T} T_i^t) \cup (\bigcup_{t(x_i)=F} T_i^f) \cup (\bigcup_{j=1}^m \{(z_j[j], s_1[j], s_2[j])\}) \cup G'$

ここで、$z_j$は$C_j$に含まれるリテラルのうち、割り当て$t$によってTrueとなるものです。3SATが充足可能であることからこのようなリテラルは必ず1つ以上存在します。

この$M'$が完全3次元マッチングであることを、以下の3つのステップで示します:

1. **$M'$の要素が互いに素であることの証明**
   
   以下の点から、$M'$の要素が互いに素であることがわかります:
   - $T_i^t$と$T_i^f$はそれぞれ異なる変数$x_i$について選ばれるため、互いに素です
   - $T_i^t$内の要素は異なる$j$について$(\bar{x}_i[j], a_i[j], b_i[j])$の形を持ち、互いに素です
   - $T_i^f$内の要素は$(x_i[j], a_i[j+1], b_i[j])$の形を持ち（ただし$j=m$のときは$a_i[1]$）、これらも互いに素です
   - 各節$c_j$からは1つの要素$(z_j[j], s_1[j], s_2[j])$のみを選んでおり、異なる$j$について$s_1[j], s_2[j]$は互いに素です
   - $G'$は未使用の$x_i[j], \bar{x}_i[j]$と新しい$g_1[k], g_2[k]$を使用するため、他の要素とは互いに素です

2. **すべての要素がカバーされることの証明**
   
   以下の点から、すべての要素が正確に1回ずつカバーされることがわかります:
   
   a. 各$x_i$について:
      - $t(x_i) = T$のとき:
        - $T_i^t$により$\bar{x}_i[j]$がすべてカバーされる
        - 残りの要素のうち、$m$個は$(\bigcup_{j = 1}^{m} \{(z_j[j], s_1[j], s_2[j])\})$により
        - $m(n-1)$個は$G'$によりカバーされる
      - $t(x_i) = F$のとき:
        - $T_i^f$により$x_i[j]$がすべてカバーされる
        - 残りの要素のうち、$m$個は$(\bigcup_{j = 1}^{m} \{(z_j[j], s_1[j], s_2[j])\})$により
        - $m(n-1)$個は$G'$によりカバーされる
   
   b. その他の要素について:
      - $A$の要素:$T_i^t$または$T_i^f$により、各$a_i[j]$がちょうど1回カバーされる
      - $B$の要素:$T_i^t$または$T_i^f$により、各$b_i[j]$がちょうど1回カバーされる
      - $S_1, S_2$の要素:各節$c_j$から選んだ1つの要素により、各$s_1[j], s_2[j]$がちょうど1回カバーされる
      - $G_1, G_2$の要素:$G'$により、残りの要素とともにカバーされる

3. **$G'$の具体的な構成**
   
   $G'$は以下の手順で構成できることを示します:
   - 各$x_i, j$について、$t(x_i) = T$のとき$x_i[j]$が、$t(x_i) = F$のとき$\bar{x}_i[j]$が未使用
   - 加えて、特定の節を真にするためのリテラルの1つが$z_j$として選ばれ、これが$m$個
   - 残りの$m(n-1)$個を$G'$に割り当てる
   - $g_1[k], g_2[k]$は$1 \leq k \leq m(n-1)$で定義され、十分な数がある
   - したがって、未使用の要素をこれらの$g_1[k], g_2[k]$と組み合わせて$G'$を構成できる

以上の3点により、構成した$M'$が完全3次元マッチングとなることが示されました。

以下にこの変換の具体例を示します。

![3DM還元の例](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3470024/4d839cd3-96f6-17c3-d9d4-0160a23b98f4.jpeg
)

#### 4. 充足可能性の保存（⇐方向）

完全3次元マッチングが存在する場合、$a_i$と$b_i$の組み合わせが$T_i^t$または$T_i^f$により一意に決定されるため、対応する変数$x_i$の真偽値割り当てが決定され、元の3SATインスタンスの充足可能性が導かれます。

## 結論

以上の証明により、以下が示されました:

1. $3DM \in NP$
2. $3SAT \leq_m 3DM$（多項式時間還元可能）

したがって、3DMはNP完全であることが証明できました。

## 参考文献

1. Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.
2. Karp, R. M. (1972). Reducibility among Combinatorial Problems. In Complexity of Computer Computations (pp. 85-103).