### 3.7.2. 3-SAT

Denotes the fact that, by reduction to 3 -SAT, deciding whether a constraint has a solution or not was shown to be NP -hard. The 3 -SAT problem can be described as follows: given a collection $C$ of clauses involving a set of variables $V$, where each clause has exactly 3 variables, is there a truth assignment for $V$ that satisfies all the clauses of $C$?