3.7.1. 3-dimensional-matching

Denotes 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?