3.7.1. 3-dimensional-matching

Denotes the fact that, by reduction to 3 -dimensional -matching, deciding whether a constraint has a solution or not was shown to be NP -hard. The 3 -dimensional -matching problem can be described as follows: given a set SX×Y×Z, where X, Y and Z are disjoint sets having the same number of elements m, does S contain a subset M of m elements such that no two elements of M agree in any coordinate?