Numerical 3-dimensional matching is an

NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

decision problem. It is given by three

multisets In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the ''multiplicity'' of ...

integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...

X

Y

and

Z

, each containing

k

elements, and a bound

b

. The goal is to select a subset

M

X\times Y\times Z

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

P16 p16 (also known as p16INK4a, cyclin-dependent kinase inhibitor 2A, CDKN2A, multiple tumor suppressor 1 and numerous other synonyms), is a protein that slows cell division by slowing the progression of the cell cycle from the G1 phase to the ...

in.Garey, Michael R. and David S. Johnson (1979), Computers and Intractability; A Guide to the Theory of NP-Completeness.

Example

Take

X=\

Y=\

and

Z=\

, and

b=10

. This instance has a solution, namely

\

. Note that each triple sums to

b=10

. The set

\

is not a solution for several reasons: not every number is used (a

4\in X

is missing), a number is used too often (the

3\in X

) and not every triple sums to

b

(since

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

for the same

X

Y

and

Z

, this problem would have no solution (all numbers sum to

30

, which is not equal to

k\cdot b=33

in this case).

Proof of NP-completeness

The numerical 3-d matching problem is problem

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 The 3-partition problem is a strongly NP-complete problem in computer science. The problem is to decide whether a given multiset of integers can be partitioned into triplets that all have the same sum. More precisely: * Input: a multiset ''S'' ...

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.

References

{{reflist Strongly NP-complete problems

Example

Related problems

Proof of NP-completeness

References