- Numerical 3-dimensional matching
-
Numerical 3-dimensional matching is a strongly 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 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 [1].
Contents
Example
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 is missing), a number is used too often (the ) and not every triple sums to b (since ). 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 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.
Proof of NP-completeness
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".[1] 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.
References
- ^ a b Garey, Michael R. and David S. Johnson (1979), Computers and Intractability; A Guide to the Theory of NP-Completeness. ISBN 0-7167-1045-5
Categories:- Strongly NP-complete problems
Wikimedia Foundation. 2010.