3.7.2. 3-SAT

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