数値3次元マッチング

数値3次元マッチングはNP完全決定問題である。これは3つの整数の多重集合によって与えられる。${\displaystyle X}$、${\displaystyle Y}$そして${\displaystyle Z}$それぞれに${\displaystyle k}$要素、および境界${\displaystyle b}$目標は部分集合を選択することです${\displaystyle M}$の${\displaystyle X\times Y\times Z}$すべての整数${\displaystyle X}$、${\displaystyle Y}$そして${\displaystyle Z}$ちょうど 1 回発生し、すべての 3 つに対して${\displaystyle (x,y,z)}$サブセット内で${\displaystyle x+y+z=b}$保持します。この問題は [SP16] とラベル付けされています。^{[ 1 ]}

取る${\displaystyle X=\{3,4,4\}}$、${\displaystyle Y=\{1,4,6\}}$そして${\displaystyle Z=\{1,2,5\}}$、 そして${\displaystyle b=10}$この事例には解決策があります。${\displaystyle \{(3,6,1),(4,4,2),(4,1,5)\}}$各3つの合計は${\displaystyle b=10}$セット${\displaystyle \{(3,6,1),(3,4,2),(4,1,5)\}}$いくつかの理由から、これは解決策ではありません。すべての数字が使用されるわけではありません（${\displaystyle 4\in X}$が欠落している場合)、数字が頻繁に使用されすぎている場合(${\displaystyle 3\in X}$）そしてすべての3つが合計されるわけではない${\displaystyle b}$（以来${\displaystyle 3+4+2=9\neq b=10}$しかし、この問題には少なくとも1つの解決策があり、それが決定問題で私たちが関心を持っている特性です。${\displaystyle b=11}$同じもの${\displaystyle X}$、${\displaystyle Y}$そして${\displaystyle Z}$この問題には解がありません（すべての数字の合計は${\displaystyle 30}$これは等しくない${\displaystyle k\cdot b=33}$この場合）。

数値3次元マッチング問題のすべてのインスタンスは、 3分割問題と3次元マッチング問題の両方のインスタンスである。

数値3Dマッチングのインスタンスが与えられた場合、辺を持つ三部ハイパーグラフを構築する。${\displaystyle X}$、${\displaystyle Y}$そして${\displaystyle Z}$ハイパーエッジが存在する場所${\displaystyle (x,y,z)}$⁠の場合に限り${\displaystyle x+y+z=T}$このハイパーグラフにおけるマッチングは、ABC分割問題の解に対応する。

数値3次元マッチング問題は、GareyとJohnsonによる問題[SP16]である。^{[ 1 ]}彼らはNP完全であると主張し、^{[ 2 ]}を参照しているが、その主張は文献では証明されていない。関連する問題である3分割問題のNP困難性は、 ^{[ 1 ]}において4分割問題による3次元マッチング問題からの還元によって証明されている。数値3次元マッチング問題のNP完全性を証明するには、証明方法は同様であるが、数値4次元マッチング問題による3次元マッチング問題からの還元を用いる必要がある。NP困難性の明示的な証明は、後の論文で示されている。

• Yu、Hoogeveen、Lenstra ^{[ 3 ]}は、3 つのセットのうち 2 つが 1,..., kという数のみを含む、非常に制限されたバージョンの数値 3 次元マッチングの NP 困難性を証明しています。
• Caracciolo、Fichera、およびSportiello ^{[ 4 ]}は、NAE-SATからの還元によって、数値3次元マッチングおよび関連問題のNP困難性を証明しています。還元は線形であり、つまり、縮小されたインスタンスのサイズは、元のインスタンスのサイズの線形関数です。