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.

  1. Let Q be a problem in NP.
  2. 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.
  3. 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
  4. The total time is O(s^j), which means that the space requirement is at most O(s^j) as well
  5. 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).
  6. 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)).
  7. 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.
  8. 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.