Previous Lesson

Next Lesson
Now that we have shown that CNFSAT is NPcomplete we can use it to
show many other problems are NPcomplete via the following lemma.
Lemma: If a set A is NPcomplete and B is in NP and A
polynomialtime reduces to B then B is also NPcomplete.
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 3SAT, the set of satisfiable 3CNF formula with
exactly 3 literals in each clause. 3SAT is in NP by just guessing
an assignment and verifying that it satisfies the formula. To show
3SAT is NPcomplete we will reduce 3CNF to 3SAT. 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 k1 literals and one with 3 literals and then
recurse. Suppose C = x_{1} OR ... OR x_{k}. We add a
new variable w and replace C with X_{1} OR ... OR
X_{k2} OR w and w OR x_{k1} 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 NPcomplete problems and we could spend
many lessons showing that they are NPcomplete. Personally, I find
NPcompleteness 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 NPcomplete problems are out there. The best source for
all things NPcomplete still remains the excellent book
of Garey and Johnson.