Numerical 3-dimensional matching is an NP-complete decision problem. It is given by three multisets of integers X , Y and Z , each containing k elements, and a bound b . The goal is to select a subset M of X × Y × Z such that every integer in X , Y and Z occurs exactly once and that for every triple ( x , y , z ) in the subset x + y + z = b holds. This problem is labeled as [SP16] in.
Take X = { 3 , 4 , 4 } , Y = { 1 , 4 , 6 } and Z = { 1 , 2 , 5 } , and b = 10 . This instance has a solution, namely { ( 3 , 6 , 1 ) , ( 4 , 4 , 2 ) , ( 4 , 1 , 5 ) } . Note that each triple sums to b = 10 . The set { ( 3 , 6 , 1 ) , ( 3 , 4 , 2 ) , ( 4 , 1 , 5 ) } is not a solution for several reasons: not every number is used (a 4 ∈ X is missing), a number is used too often (the 3 ∈ X ) and not every triple sums to b (since 3 + 4 + 2 = 9 ≠ b = 10 ). However, there is at least one solution to this problem, which is the property we are interested in with decision problems. If we would take b = 11 for the same X , Y and Z , this problem would have no solution (all numbers sum to 30 , which is not equal to k ⋅ b = 33 in this case).
Every instance of the Numerical 3-dimensional matching problem is an instance of both the 3-partition problem, and the 3-dimensional matching problem.
NP-completeness of the 3-partition problem is stated by Garey and Johnson in "Computers and Intractability; A Guide to the Theory of NP-Completeness", which references to this problem with the code [SP16]. It is done by a reduction from 3-dimensional matching via 4-partition. To prove NP-completeness of the numerical 3-dimensional matching, the proof is similar, but a reduction from 3-dimensional matching via the numerical 4-dimensional matching problem should be used.
