'''Numerical 3-dimensional matching''' is an NP-complete decision problem. It is given by three multisets of integers <math>X</math>, <math>Y</math> and <math>Z</math>, each containing <math>k</math> elements, and a bound <math>b</math>. The goal is to select a subset <math>M</math> of <math>X\times Y\times Z</math> such that every integer in <math>X</math>, <math>Y</math> and <math>Z</math> occurs exactly once and that for every triple <math>(x,y,z)</math> in the subset <math>x+y+z=b</math> holds. This problem is labeled as [SP16] in.<ref name=garey>Garey, Michael R. and David S. Johnson (1979), Computers and Intractability; A Guide to the Theory of NP-Completeness. {{ISBN|0-7167-1045-5}}</ref>

== Example == Take <math>X=\{3,4,4\}</math>, <math>Y=\{1,4,6\}</math> and <math>Z=\{1,2,5\}</math>, and <math>b=10</math>. This instance has a solution, namely <math>\{(3,6,1), (4,4,2), (4,1,5)\}</math>. Note that each triple sums to <math>b=10</math>. The set <math>\{(3,6,1), (3,4,2), (4,1,5)\}</math> is not a solution for several reasons: not every number is used (a <math>4\in X</math> is missing), a number is used too often (the <math>3\in X</math>) and not every triple sums to <math>b</math> (since <math>3+4+2=9\neq b=10</math>). 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 <math>b=11</math> for the same <math>X</math>, <math>Y</math> and <math>Z</math>, this problem would have no solution (all numbers sum to <math>30</math>, which is not equal to <math>k\cdot b=33</math> 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 <math>X</math>, <math>Y</math> and <math>Z</math>, where there is an hyperedge {{tmath|(x, y, z)}} if and only if <math>x+y+z = T</math>. 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.<ref name=garey/> They claim it is NP-complete, and refer to,<ref>{{Cite journal |last1=Garey |first1=M. R. |last2=Johnson |first2=D. S. |date=December 1975 |title=Complexity Results for Multiprocessor Scheduling under Resource Constraints |url=http://epubs.siam.org/doi/10.1137/0204035 |journal=SIAM Journal on Computing |language=en |volume=4 |issue=4 |pages=397–411 |doi=10.1137/0204035 |issn=0097-5397|url-access=subscription }}</ref> but the claim is not proved at that source. The NP-hardness of the related problem 3-partition is done in <ref name="garey" /> 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<ref>{{Cite journal |last1=Yu |first1=Wenci |last2=Hoogeveen |first2=Han |last3=Lenstra |first3=Jan Karel |date=2004-09-01 |title=Minimizing Makespan in a Two-Machine Flow Shop with Delays and Unit-Time Operations is NP-Hard |url=https://doi.org/10.1023/B:JOSH.0000036858.59787.c2 |journal=Journal of Scheduling |language=en |volume=7 |issue=5 |pages=333–348 |doi=10.1023/B:JOSH.0000036858.59787.c2 |issn=1099-1425|url-access=subscription }}</ref> 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<ref>{{Citation |last1=Caracciolo |first1=Sergio |title=One-in-Two-Matching Problem is NP-complete |date=2006-04-28 |last2=Fichera |first2=Davide |last3=Sportiello |first3=Andrea|arxiv=cs/0604113 |bibcode=2006cs........4113C }}</ref> 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.

== References == {{reflist}}

Category:Strongly NP-complete problems