Numerical 3-dimensional matching is an 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
X
×
Y
×
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 [SP16] in.
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
4
∈
X
is missing), a number is used too often (the
3
∈
X
) and not every triple sums to
b
(since
3
+
4
+
2
=
9
≠
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
⋅
b
=
33
in this case).
Every instance of the Numerical 3-dimensional matching problem is an instance of both the 3-partition problem, and the 3-dimensional matching problem.
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", which references to this problem with the code [SP16]. 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.
