* Linear Programming	 15-451			11/05/03
* NP and NP-completeness

Questions about Linear Programming?  Here's an example of modeling a
problem as an LP:

   Modeling MULTICOMMODITY FLOW as a linear program.

   The multicommodity flow problem is just like the standard network flow
   problem except we have $p$ sources $s_1, \ldots, s_p$ and $p$ sinks
   $t_1, \ldots, t_p$.  The stuff flowing from $s_1$ has to go to $t_1$,
   the stuff from $s_2$ has to go to $t_2$, and so on.  For each sink
   $t_i$ we have a {\em demand} $d_i$.  (E.g., we need to get $d_1$
   trucks from $s_1$ to $t_1$, $d_2$ trucks from $s_2$ to $t_2$, and so
   on.)  Each directed edge has a capacity indicating the maximum
   total amount of traffic that can go on it.  Want to know if problem
   is feasible.
   
   How to set up as an LP?
   
   What are the variables? for each commodity i and each edge
      e we have a variable x_{ei}.  

   What are the constraints?
   - for all i, for all e, x_{ei} >=0.
   - for all e,  sum_i x_{ie} <= c_e.
   - for all i, for all v (except s_i,t_i), 
           sum_{e in in(v)} x_{ei} = sum_{e in out(v)} x_{ei}
   - for all i, sum_{e in in(t_i)} x_{ei} - sum_{e in out(t_i)} x_{ei} >= d_i
   
   in(v) means the set of edges going into v.


NP and NP-completeness
======================

Search vs Decision:

The Hamiltonian path problem is: given a graph G, is there are tour
that visits each vertex exactly once?  Why is the problem in NP?  How
could you use an algorithm that just answers yes or no to actually
*find* the tour?  This is called "reducing the search problem to the
decision problem".


Here is another interesting problem:

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?

I claim that if we had an algorithm to solve this problem, then we
could solve solve ANY problem in NP.  Here's why (with a little
handwaving): 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).  What it
means to "check" is that 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.  So, to
solve problem A, given some instance x, all we need to do is create a
circuit C_x such that C_x(y) = V(x,y).  If we think of V as a computer
program, we can do this (handwaving) by unrolling the loops of V, and
having each layer of the circuit encode one time step of V's
computation.  Remember from 15-251 that a computer is just NAND gates
with memory....  We then hardwire the "x" part of the input wires to
our given instance "x", producing the circuit C_x.  Given this, all we
now need to do is feed C_x into our supposed algorithm for
CIRCUIT-SAT, and see if it tells us whether some y exists such that
C_x(y)=1, solving problem A.

The above is a (handwavy) proof that CIRCUIT-SAT is NP-COMPLETE.  This
means that if you could solve this problem, then you can solve any
problem in NP.  Will see more of this in lecture on Thurs.

Now that we have one NP-complete problem, we can use it to show lots
of other problems are NP-complete too.