Numerical 3-dimensional matching is an NP-complete decision problem.
It is given by three multisets of integers
elements, and a bound
The goal is to select a subset
occurs exactly once and that for every triple
This problem is labeled as [SP16] in.
This instance has a solution, namely
Note that each triple sums to
is not a solution for several reasons: not every number is used (a
is missing), a number is used too often (the
) and not every triple sums to
However, there is at least one solution to this problem, which is the property we are interested in with decision problems.
, this problem would have no solution (all numbers sum to
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
A matching in this hypergraph corresponds to a solution to ABC-partition.
The numerical 3-d matching problem is problem [SP16] of Garey and Johnson.
[1] They claim it is NP-complete, and refer to,[2] but the claim is not proved at that source.
The NP-hardness of the related problem 3-partition is done in [1] 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: