背景： Exact-3D-Matching問題は次のように定義されます（定義はJeffの講義ノート：講義29：NP困難な問題からのものです。 3次元マッチング）を参照してください：
Exact-3D-マッチング：セット$ S $と$ S $の3要素サブセットのコレクション triples が与えられた場合、$ S $を正確にカバーするばらばらのトリプルのサブコレクションがあります。 ？
3-Partition問題は次のように定義されます（これも講義29：NP困難な問題。 3パーティションの問題も参照できます。）：
$ 3n $の整数のセット$ S $が与えられた場合、すべてのサブセットがまったく同じ合計になるように、$ n $のばらばらの3要素サブセットに分割できますか？
3-Partition問題は、NP完全
問題があります。そして、Exact-3D-Matching問題のNP完全性は、3SAT問題をそれに還元することによって証明されます（両方とも本
コンピューターと難易度：NP完全性の理論へのガイド）。
問題：私の問題は次のとおりです。
3-Partitionの問題をそれに減らすことで問題が発生しますか？
論文も見つかりませんでした講義ノート。
コメント
回答
この削減はうまくいくと思います：
3つのパーティションのインスタンスがある場合：$ n $整数$ a_1、\ ldots、a_ {3n} $およびターゲット合計$ B $;各整数を一意の識別子$ \ hat {a_i} $でマークします。次に、3要素のサブセット$ C_j = \ {\ hat {a} _ {i_1}、\ hat {a} _ {i_2}、\ hat {a} _ {i_3} \} $のコレクションを$ a_ {i_1} + a_ {i_2} + a_ {i_3} = B $および$ i_1 \ neq i_2 \ neq i_3 $（コレクションには$ O（n ^ 3）$要素があります）。
オリジナル3-PARTITION問題は、$ S = \ hat {a} _ {1}、\ ldotsをカバーする正確な3Dマッチング$ C_ {j_1}、\ ldots、C_ {j_n} $が存在する場合にのみ解決策があります。 、\ hat {a} _ {3n} $。
たとえば、$ A = \ {5,4,3,3,3,2,2,1,1 \}の場合、B = 8 $ビルド：$ S = \ {5a、4a、3a、3b、3c、2a、2b、1a、1b \} $および3要素サブセットのコレクション：
C1 = { 5a, 2a, 1a } C2 = { 5a, 2a, 1b } C3 = { 5a, 2b, 1a } C4 = { 5a, 2b, 1b } C5 = { 4a, 3a, 1a } C6 = { 4a, 3a, 1b } C7 = { 4a, 3b, 1a } C8 = { 4a, 3b, 1b } C9 = { 4a, 3c, 1a } C10 = { 4a, 3c, 1b } C11 = { 4a, 2a, 2b } C12 = { 3a, 3b, 2a } C13 = { 3a, 3b, 2b } C14 = { 3a, 3c, 2a } C15 = { 3a, 3c, 2b } C16 = { 3b, 3c, 2a } C17 = { 3b, 3c, 2b } Exact-3D-MATCHINGは次の式で与えられます。
C1 = { 5a, 2a, 1a } C6 = { 4a, 3a, 1b } C16 = { 3b, 3c, 2b } これは、元の3パーティション問題の有効なソリューションも一意に識別します。 。
コメント
- はい、機能します。各$ a_i $を一意としてマークできませんでした。ありがとう。
Exact-3D-Matchingから3-Partitionへの削減は、教科書で簡単に見つけることができます（削減自体は簡単ではありませんが）。したがって、私は逆方向を求めています。タイトルを変更して回答を受け入れます。