next up previous contents index CD CD Algorithms
Next: The Theory of NP-Completeness Up: Intractable Problems and Approximations Previous: Clique and Independent Set


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 tex2html_wrap_inline26094 either true or false so that each clause contains at least one true literal? This can be made clearer with two examples. Suppose that tex2html_wrap_inline26096 over the Boolean variables tex2html_wrap_inline26098 . We use tex2html_wrap_inline26100 to denote the complement of the variable tex2html_wrap_inline26102 , so we would get credit for satisfying a particular clause containing tex2html_wrap_inline26104 if tex2html_wrap_inline26106 , or a clause containing tex2html_wrap_inline26108 if tex2html_wrap_inline26110 . 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 tex2html_wrap_inline26112 can be satisfied by simply setting tex2html_wrap_inline26114 or tex2html_wrap_inline26116 . However, consider the set of clauses tex2html_wrap_inline26118 . There can be no satisfying assignment because tex2html_wrap_inline26120 must be tex2html_wrap_inline26122 in order to satisfy the third clause, which means that tex2html_wrap_inline26124 must be tex2html_wrap_inline26126 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