20090921


We started with a review of the key concepts we have developed so far:

The use of computational complexity of the best-possible algorithm for a problem as our measure of the difficulty of that problem.

Decision problems

The class P

The class NP

Reduction from one problem to another

CNF-SAT

The Cook-Levin Theorem

NP-Complete Problems



We continued with a discussion of why this is important: the implication of the Cook-Levin Theorem is that if ... IF ... we could find a polynomial time algorithm to solve CNF-SAT, we could solve every problem in NP in polynomial time ... in other words, we would have proved that P = NP.  Most researchers in the computational complexity field believe that P != NP, and therefore believe that there does not exist any polynomial time algorithm for CNF-SAT.

Well, who cares?  CNF-SAT may seem like an abstract problem that is not likely to be encountered very often in practice.  And even though the CL Theorem tells us that any problem X (in NP) can be reduced to CNF-SAT, the reduction is complicated - finding a polynomial time algorithm for CNF-SAT might not be so useful after all.

So far in our story, we only know one NP-Complete problem, CNF-SAT.  Suppose we had a new problem Z, and we wanted to prove that Z is NP-Complete.  There are three possibilities:
    1.  Recreate the CL Theorem: show that all problems in NP reduce to Z.  This is not appealing - the proof of the CL Theorem is long and complicated
    2.  Prove that CNF-SAT reduces to Z.  This would prove that Z is NP-Complete, because reduction is transitive - we already know that all problems in NP reduce to CNF-SAT.  The reduction from CNF-SAT to Z would show that all problems in NP reduce to Z.  This is better than option 1, but can still involve a lot of work - as we will see next day.
    3.  Find some known NP-Complete problem (let's call it Y) that resembles Z.  Prove that Y reduces to Z.  This proves that Z is NP-Complete, using the same reasoning as in option 2.  This is the best option because it usually involves relatively little work.

Fortunately, Option 3 is not only appealing but practical.  Since the early 1970's, thousands of NP-Complete problems have been identified.  Over the next couple of days we will meet some of them.