Foundations of Complexity Lesson 15: More NP-complete Problems

Previous Lesson | Next Lesson

Now that we have shown that CNF-SAT is NP-complete we can use it to show many other problems are NP-complete via the following lemma.

Lemma: If a set A is NP-complete and B is in NP and A polynomial-time reduces to B then B is also NP-complete.

Proof: Let C be an arbitrary set in NP. We need to show C reduces to B. We know C reduces to A (since A is complete) and A reduces to B and it is a simple exercise to see that reductions are transitive. ◊

For example consider 3-SAT, the set of satisfiable 3-CNF formula with exactly 3 literals in each clause. 3-SAT is in NP by just guessing an assignment and verifying that it satisfies the formula. To show 3-SAT is NP-complete we will reduce 3-CNF to 3-SAT. We take each clause and convert it to a set of clauses each with three literals. We will add additional variables for this reduction.

If the clause C has three literals then no conversion is necessary.

If the clause C has two literals something like C = x OR y. We use a new variable z and replace C with two clauses, x OR y OR z and x OR y OR z. Notice that C is satisfied if and only if both new clauses can be satisfied.

If the clause C has one literal like C = x, we add two new variables, u and v and replace C with four new clauses, x OR u OR v, x OR u OR v, x OR u OR v and x OR u OR v.

If the clause C has k literals for k>3, we will replace C by two clauses, one with k-1 literals and one with 3 literals and then recurse. Suppose C = x₁ OR ... OR x_k. We add a new variable w and replace C with X₁ OR ... OR X_k-2 OR w and w OR x_k-1 OR x_k. Again note that C is satisfied only if both of the new clauses are satisfied with some value for w.

That is the reduction and the proof that it works is straightforward.

There are many many natural NP-complete problems and we could spend many lessons showing that they are NP-complete. Personally, I find NP-completeness proofs more algorithmic than complexity and I will instead focus on relationships of complexity classes in future lessons.

This site is a collection of optimization problems but it also gives you a good idea of what NP-complete problems are out there. The best source for all things NP-complete still remains the excellent book of Garey and Johnson.