15-451 Algorithms               11/10/04
* Linear programming
* NP and NP-completeness
=======================================================================

* Linear programming:
  - if you didn't do LP last time, you might want to go over the LP
    parts of the hwk that was due yesterday (fractional set-cover
    and/or multicommodity flow).  Have a student present their answer.

* NP and NP-completeness

In order to get going with the whole theory of NP-completeness, we
need to have some NP-complete problem to begin with.  Here is a proof
sketch from first principles that the following problem, called
CIRCUIT-SAT, is NP-complete.

  CIRCUIT-SAT: Given a circuit of NAND gates with a single output and no
  loops (some of the inputs may be hardwired).  Question: is there a
  setting of the inputs that causes the circuit to output 1?

Proof Sketch:

First of all, it is clearly in NP, since you can just guess the input
and try it.

Now, suppose some problem A is in NP.  That means there is a
polynomial-time verifier V that takes in an instance x and a
solution/proof y, and then checks to see if y is really a
solution/proof for x.  (E.g., x is a graph and y is a tour).  In other
words, if x is a NO instance, then there should not exist any y such
that V(x,y)=1.  But, if x is a YES instance, then there should exist
some y that causes V(x,y) to output 1.  We are now going to use V to
reduce problem A to CIRCUIT-SAT.  Specifically, given some instance x,
we want to create a circuit C_x such that C_x(y) = V(x,y).  If we can
do this, then C_x is a YES-instance of CIRCUIT-SAT (i.e., there exists
y such that C_x(y)=1) iff x was a YES-instance of A (i.e., there
exists y such that V(x,y)=1).  

How are we going to convert V and x into a circuit C_x?  If we think
of V as a computer program, we can do this by unrolling
the loops of V, and having each layer of the circuit encode one time
step of V's computation.  The width of C_x will be the amount of
memory used by V, and the depth of C_x will be the amount of time used
by V.  (Remember from 15-251 that a computer is just NAND gates with
a clock, which means we can encode one step of computation by one
layer of circuit.)  Since V is polytime, this circuit will have
polynomial size.  We then hardwire the "x" part of the input wires to our
given instance "x", producing the circuit C_x.  

We have now shown how to reduce any arbitrary problem A in NP to
CIRCUIT-SAT.  In other words, if we had an oracle for CIRCUIT-SAT, we
could use it to solve any problem A in NP: given an input x we run the
above procedure to produce C_x and then feed C_x into our oracle.
I.e., we have shown that CIRCUIT-SAT is NP-complete.


[If there is time, do reduction below]

We can use this to prove that 3-SAT is NP-complete too.

This reduction is important (and a little tricky) because 3-SAT looks
so much simpler than Circuit-SAT.  Nonetheless, we're going to prove
that any algorithm to solve 3-SAT could be used to solve general
circuit-SAT too.  To prove this, we want to show how we can take a
circuit-SAT instance (i.e., a circuit C where we want to know if there
exists an input z that makes C(z)=1) and convert it into a 3-SAT
instance that is satisfiable *iff* the circuit we were given is satisfiable.

REDUCTION:  We will create one variable for each *wire* in the circuit
C.  Say we have some gate g whose inputs are wires y_1 and y_2, and
whose output wire is y_3.  Since g is a NAND gate, we want to make 
sure that the output is NOT the AND of the two inputs.  We can write
this as:
     (y_1 OR y_2 OR y_3)      // if y_1=0 and y_2=0 then we can't have y_3=0
 AND (y_1 OR not(y_2) OR y_3) // if y_1=0 and y_2=1 then we can't have y_3=0
 AND (not(y_1) OR y_2 OR y_3) // if y_1=1 and y_2=0 then we can't have y_3=0
 AND (not(y_1) OR not(y_2) OR not(y_3))  // can't have all three = 1.

We will do this for all gates in the circuit.  Now, we will also have
variables z_1,...,z_n for the input bits to C, and force any wire y_j
connected to input z_i to have the same value as variable z_i: (y_j OR
not(z_i)) AND (not(y_j) or z_i) Finally, we add one more clause saying
that we want the output to be 1.  This is easy: if y_m is the output
wire, then we just add the clause (y_m).  In other words, we are
asking: is there an input and a setting of all the wires such that the
output of the circuit is equal to 1, and each gate is doing what it's
supposed to?  So, the 3-CNF formula produced is satisfiable if and
only if the circuit has a setting of inputs that causes it to output
1. The size of the formula is polynomial (actually, linear) in the
size of the circuit.  The construction can be done in polynomial
(actually, linear) time.  So, if we had a polynomial-time algorithm to
solve 3-SAT, then we could solve circuit-SAT in poly time too.