Numerical 3-dimensional matching is an NP-complete decision problem. It is given by three multisets of integers X {\displaystyle X}, Y {\displaystyle Y} and Z {\displaystyle Z}, each containing k {\displaystyle k} elements, and a bound b {\displaystyle b}. The goal is to select a subset M {\displaystyle M} of X × Y × Z {\displaystyle X\times Y\times Z} such that every integer in X {\displaystyle X}, Y {\displaystyle Y} and Z {\displaystyle Z} occurs exactly once and that for every triple ( x , y , z ) {\displaystyle (x,y,z)} in the subset x + y + z = b {\displaystyle x+y+z=b} holds. This problem is labeled as [SP16] in.

Example

Take X = { 3 , 4 , 4 } {\displaystyle X=\{3,4,4\}}, Y = { 1 , 4 , 6 } {\displaystyle Y=\{1,4,6\}} and Z = { 1 , 2 , 5 } {\displaystyle Z=\{1,2,5\}}, and b = 10 {\displaystyle b=10}. This instance has a solution, namely { ( 3 , 6 , 1 ) , ( 4 , 4 , 2 ) , ( 4 , 1 , 5 ) } {\displaystyle \{(3,6,1),(4,4,2),(4,1,5)\}}. Note that each triple sums to b = 10 {\displaystyle b=10}. The set { ( 3 , 6 , 1 ) , ( 3 , 4 , 2 ) , ( 4 , 1 , 5 ) } {\displaystyle \{(3,6,1),(3,4,2),(4,1,5)\}} is not a solution for several reasons: not every number is used (a 4 ∈ X {\displaystyle 4\in X} is missing), a number is used too often (the 3 ∈ X {\displaystyle 3\in X}) and not every triple sums to b {\displaystyle b} (since 3 + 4 + 2 = 9 ≠ b = 10 {\displaystyle 3+4+2=9\neq 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 {\displaystyle b=11} for the same X {\displaystyle X}, Y {\displaystyle Y} and Z {\displaystyle Z}, this problem would have no solution (all numbers sum to 30 {\displaystyle 30}, which is not equal to k ⋅ b = 33 {\displaystyle k\cdot b=33} in this case).

Related problems

Every instance of the Numerical 3-dimensional matching problem is an instance of both the 3-partition problem, and the 3-dimensional matching problem.

Given an instance of numeric 3d-matching , construct a tripartite hypergraph with sides X {\displaystyle X}, Y {\displaystyle Y} and Z {\displaystyle Z}, where there is an hyperedge ⁠( x , y , z ) {\displaystyle (x,y,z)}⁠ if and only if x + y + z = T {\displaystyle x+y+z=T}. A matching in this hypergraph corresponds to a solution to ABC-partition.

Proof of NP-completeness

The numerical 3-d matching problem is problem [SP16] of Garey and Johnson. They claim it is NP-complete, and refer to, but the claim is not proved at that source. The NP-hardness of the related problem 3-partition is done in by a reduction from 3-dimensional matching via 4-partition. To prove NP-completeness of the numerical 3-dimensional matching, the proof should be similar, but a reduction from 3-dimensional matching via the numerical 4-dimensional matching problem should be used. Explicit proofs of NP-hardness are given in later papers:

  • Yu, Hoogeveen and Lenstra prove NP-hardness of a very restricted version of Numerical 3-Dimensional Matching, in which two of the three sets contain only the numbers 1,...,k.
  • Caracciolo, Fichera, and Sportiello prove NP-hardness of Numerical 3-Dimensional Matching and related problems by reduction from NAE-SAT. The reduction is linear, that is, the size of the reduced instance is a linear function of the size of the original instance.