Reading
These notes and
Unit 6 sections 4 and 5.
Quiz questions
None!
CIRCUIT-SAT
We introduced the CIRCUIT-SAT problem.
Moreover, we proved that it is in the class NP,
i.e. certificates can be expressed in a number of
bits that's polynomial in the bit-length of the
description of the circuit, and we can verify these
certificates in polynomial time as well.
What's new, however, is that we will show that
every problem in NP is polynomial time reducible
to CIRCUIT-SAT. This means that if we found a
polynomial time solution to CIRCUIT-SAT, we'd
automatically have a polynomial time solution to every
problem in NP! This, of course, would win us
$1,000,000, because it would show that P = NP.
NP-Complete Problems
We have a crucial defintion:
Definition: Problem Pr is
NP-Complete if every problem in NP is polynomial time
reducible to Pr.
Of course, it's not obvious that there are actually any problems
that satsify this definition, i.e. there might not be any
NP-Complete problems! Well, don't worry, there are. In the
next section, we will show that CIRCUIT-SAT is one such problem.
CIRCUIT-SAT is NP-Complete
A problem that is in NP, and has the property that every
problem in NP is polynomial time reducible to it is called
NP-Complete. We want to prove that CIRCUIT-SAT is
NP-Complete, which means all we have left to do is to show
that every problem in NP is polynomial time reducible to
CIRCUIT-SAT!
Assume that we have a very simple model of a computer,
with registers and a program counter, etc., and let's
assume that it's pretty easily scaleable ... that is if
we want a larger memory size (and thus larger word size)
it's easy to write down a description of the expanded
machine.
- Let Q be a problem in NP.
- A certificate for an instance of Q can be
written down in O(s^i) bits, where i is the bit-length
of the description of the problem instance.
- There is a program A that runs on our simple machine
that takes a certificate for an instance of Q and verifies it
in time O(s^j), where j ≥ i
- The total time is O(s^j), which means that the
space requirement is at most O(s^j) as well
- A complete description of the "machine" running this
would be it's PC + registers + the "program" + problem
instance + certificate +
memory. PC + registers + program has constant size,
since it doesn't depend on the specific instance of
the problem. The rest depends on the problem size,
but it depends as O(s^j).
- To figure out what the
state will be at the next clock-tick, we have some
circuitry that has each bit of PC + registers + the
"program" + problem instance + certificate + memory as
input and output. We
could, however, think of the output as going to
another copy of PC + registers + the "program" + problem
instance + certficiate
+ memory --- sort of a before/after thing. This
circuit will be big, but only O(x^k), where x is the
number of bits in PC + registers + the "program" +
input + memory. So the total size of the circuitry
will be O(s^(j*k)).
- Now, to capture the whole
computation, we would need to represent each of the
O(s^j) steps, which would mean that many copies of
the machine configuration and the circuitry between
steps. So the total size of this circuit would be
O(s^j)*O(s^(j*k)) = O(s^(j*(k+1))). This is
big, but still polynomial in the input size.
- Now we have a single circuit that produces the
entire computation of our simple machine and its
program that verifies certificates. There is
some bit in memory, that is "the output" of the
verification program: 1 if the certificate is valid,
and 0 if it isn't. Now, suppose
that we view the bits of the certificates as the
unknown inputs to a CIRCUIT-SAT problem, our huge
circuit as the circuit itself, and the bit
corresponding to the verification program output as
the output of the circuit. Asking whether or not
there is a certificate for our instance of problem Q is
equivalent to asking whether this CIRCUIT-SAT problem
instance is satisfiable. And this circuit is
polynomial in size! and we can construct it in
polynomial time! So we have a polynomial time
reduction of problem Q to CIRCUIT-SAT!
Whew! That was a bit complicated, but we have now
proven that CIRCUIT-SAT is NP-Complete
Proving Other Problems NP-Complete
Consider the difficult process we went through: We
proved that CIRCUIT-SAT was in NP, then we showed how to
take
any problem in NP and reduce it in polynomial
time to CIRCUIT-SAT. Let's never do that again!
From now on, if we want to show that some problem Q is
NP-Complete, we don't have to show how to take
any problem in NP and reduce it in polynomial
time to Q ... all we have to do is show how to reduce
CIRCUIT-SAT to Q in polynomial time. That's how we'll
show that new problems are NP-Complete.