To prove the hardness of different problems using reductions,
we need to start with a single problem that is absolutely, certifiably,
undeniably hard.
The mother of all NP-complete problems is a logic problem
named *satisfiability*:

*Input:* A set of Boolean variables *V* and a set of clauses
*C* over *V*.

*Output:* Does there exist a satisfying truth assignment for *C*, i.e. a way
to set the variables either true or false so that each
clause contains at least one true literal?
This can be made clearer with two examples.
Suppose that
over the Boolean variables
.
We use to denote the complement of the variable
, so we would get credit for satisfying a particular clause containing
if , or a clause
containing if .
Therefore, satisfying a particular set of clauses involves making a series
of *n* true or false decisions, trying to find the right truth
assignment to satisfy all of them.

This example set of clauses can be satisfied by simply setting or . However, consider the set of clauses . There can be no satisfying assignment because must be in order to satisfy the third clause, which means that must be to satisfy the second clause, which then leaves the first clause unsatisfiable. Although you try, and you try, and you try and you try, you can't get no satisfaction.

Mon Jun 2 23:33:50 EDT 1997