Numerical 3-dimensional matching is an NP-complete decision problem. It is given by three multisets of integers formula_1, formula_2 and formula_3, each containing formula_4 elements, and a bound formula_5. The goal is to select a subset formula_6 of formula_7 such that every integer in formula_1, formula_2 and formula_3 occurs exactly once and that for every triple formula_11 in the subset formula_12 holds.
This problem is labeled as [SP16] in.
Example.
Take formula_13, formula_14 and formula_15, and formula_16. This instance has a solution, namely formula_17. Note that each triple sums to formula_16. The set formula_19 is not a solution for several reasons: not every number is used (a formula_20 is missing), a number is used too often (the formula_21) and not every triple sums to formula_5 (since formula_23). 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 formula_24 for the same formula_1, formula_2 and formula_3, this problem would have no solution (all numbers sum to formula_28, which is not equal to formula_29 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 formula_1, formula_2 and formula_3, where there is an hyperedge &amp;NoBreak;&amp;NoBreak; if and only if formula_33. 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:
References.
 ;templatestyles src="Reflist/styles.css" / ;