15-451 Algorithms                  11/09/05
                        recitation notes

* Recap of basic definitions of NP and NP-completeness
* Why solving any NP-complete problem would allow you to solve the
  SEARCH version of *any* problem in NP.
* An NP-completeness reduction
  [Note: I updated the CIRCUIT-SAT -> 3-SAT reduction in the lecture
  notes on the web to make it cleaner]
=================================================================

Let's define the SEARCH-VERSION of an NP-complete problem to be that of
  *finding* a witness X for the case that I is a YES-instance.

Claim: if you could solve the decision-version of any NP-complete
  problem in poly time, then you can solve the search-version of any
  problem in NP in poly time.

Proof: reduce search to decision for either SSEP (the short-solution
  existence problem) or CIRCUIT-SAT (your choice).  E.g., for SSEP,
  define V'((I, X1), X2) = V(I, X1 concatenated with X2), and then fix
  bits one at a time in X, verifying that there still is a solution.
  Or it's even easier for CIRCUIT-SAT: just start fixing input bits of
  the circuit and you get a new circuit.  Then, the next key point is
  that the generic reduction from an arbitrary problem Q in NP to SSEP
  (or CIRCUIT-SAT) mapped the witness directly across, so finding the
  witness for these problems gives you the witness for Q.  So, putting
  it all together, if you could solve the decision-version of any
  NP-Complete problem in poly time, then you could solve the decision
  version of these problems in poly time, which means you could solve
  the search version of these in poly time, which then lets you solve
  the search version of any problem in NP in poly time.

More topics:

In lecture we proved that CLIQUE is NP-complete.  How about using that
to prove NP-completeness for Independent Set and for Vertex Cover?

Let's give one more NP-completeness reduction.

INTEGER PROGRAMMING

Integer linear programming (ILP) is like linear programming, with the
additional constraint that all variables must take on integral values.
The decision version of integer programming asks whether or not there
exists a point satisfying all the constraints (for the decision
version there is no objective function).

Claim: ILP is NP-complete.

Proof:

(1) ILP is in NP.

(2) We can reduce 3SAT to ILP:

Let the variables in the 3SAT formula be x_1, x_2, ..., x_n.  We will
have corresponding variables z_1, z_2, ..., z_n in our integer linear
program.  First, restrict each variable to be 0 or 1:

0 <= z_i <= 1	  for all i

Assigning z_i=1 in the integer program represents setting x_i=true in
the formula, and assigning z_i=0 represents setting x_i=false.

For each clause like (x_1 OR not(x_2) OR x_3), have a constraint like:

z_1 + (1-z_2) + z_3 > 0.

To satisfy this inequality we must either set z_1=1 or z_2=0 or z_3=1,
which means we either set x_1=true or x_2=false or x_3=true in the
corresponding truth assignment.