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.