### 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 $S\subseteq X×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?