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.

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

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.