Next: The Theory of NP-Completeness Up: Intractable Problems and Approximations Previous: Clique and Independent Set

# Satisfiability

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.

Algorithms
Mon Jun 2 23:33:50 EDT 1997