Background: The Exact-3D-Matching problem is defined as follows (The definition is from Jeff's lecture note: Lecture 29: NP-Hard Problems. You can also refer to 3-dimensional matching):Exact-3D-Matching: Given a set $S$ and a collection of three-element subsets of $S$, called triples, is there a sub-collection of disjoint triples that exactly cover $S$?The 3-Partition problem is defined as (It is also from Lecture 29: NP-Hard Problems. You can also refer to 3-partition problem.):Given a set $S$ of $3n$ integers, can it be partitioned into $n$ disjoint three-element subsets, such that every subsets has exactly the same sum?It is known that the 3-Partition problem can be proved to be NP-complete by reducing the NP-complete Exact-3D-Matching problem to it. And the NP-completeness of the Exact-3D-Matching problem is proved by reducing the 3SAT problem to it (both are given in the book Computers and Intractability: A Guide to the Theory of NP-Completeness).Problem: My problem is:How to prove the NP-completeness of the Exact-3D-Matching problem by reducing the 3-Partition problem to it?I have found neither papers nor lecture notes on it.
How to prove the NP-completeness of the ``Exact-3D-Matching`` problem by reducing the ``3-Partition`` problem to it?
complexity theory;np complete;np hard
I think this reduction should work:Given a 3-PARTITION instance: $n$ integers $a_1,\ldots,a_{3n}$ and a target sum $B$; mark each integer with an unique identifier $\hat{a_i}$; then build a collection of 3-elements subsets $C_j = \{ \hat{a}_{i_1}, \hat{a}_{i_2}, \hat{a}_{i_3} \}$ such that $a_{i_1}+ a_{i_2}+ a_{i_3} = B$ and $i_1 \neq i_2 \neq i_3$ (the collection has $O(n^3)$ elements).The original 3-PARTITION problem has a solution if and only if there exist an EXACT-3D-MATCHING $C_{j_1}, \ldots, C_{j_n}$ that covers $S = \hat{a}_{1}, \ldots,  \hat{a}_{3n}$.For example given $A = \{5,4,3,3,3,2,2,1,1\}, B = 8$ we build:$S = \{5a,4a,3a,3b,3c,2a,2b,1a,1b\}$ and the collection of 3-elements subsets: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 }An Exact-3D-MATCHING is given by:C1  = { 5a, 2a, 1a }C6  = { 4a, 3a, 1b }C16 = { 3b, 3c, 2b }that also uniquely identifies a valid solution for the original 3-PARTITION problem.