November 24


* 2-Satisfiability

   SAT in which each clause is in conjunctive normal form
   (a conjunction of disjunctions of literals) and has two or fewer literals

   (x1vx2)^(x3v-x2)vx1v(-x1v-x2)^(x3vx4)^(-x3vx5)^(-x4v-x5)^(x4v-x3)

   The 2-Satisfiability Problem is in P

   Algorithm

      1.  Purge
	  Look for single-literal clauses and set the variables to T
	  if positive (they must be true) and F is negative (they must be false)

	  x1 = T

          Delete all clauses containing positive form of variable
	  Delete literal from clauses containing negative form of variable
	  If empty clause results then the formula is unsatisfiable

	  After O(n) steps ether the formula fails or the algorithm
	     halts with a set of two-literal clauses

	  (x3v-x2)^-x2^(x3vx4)^(-x3vx5)^(-x4v-x5)^(x4v-x3)

	  x2 = F

	  (x3vx4)^(-x3vx5)^(-x4v-x5)^(x4v-x3)

      2.  Pick a remaining variable and try purge with a T value.  If fail,
	  try again with a F value.  Two purges for each of n variables and each
	  purge takes O(n) steps, so this requires a polynomial number of steps.

	  x3 = T

	  x5^(-x4v-x5)^x4

	     x5 = T
	     -x4^x4
	     This fails

	  x3 = F

	  x4^(-x4v-x5)

	     x4 = T
	     -x5
	     x5 = F
             This succeeds

	  


* NP

   Many of the problems with an exponential run time can actually be solved
   in polynomial time with a Nondeterministic Turing Machine.

   NP is the class of all languages that are decided by a polynomially bounded
   nondeterministic Turing Machine.

   NP means "nondeterministically polynomial"

   Remember that M decides a language if for each string in L, at least one
   computation accepts the input.
   Some or all other computations can reject input.

   Only need one path that succeeds.


* SAT in NP

   There exists a nondeterministic TM M that decides in polynomial time all
   encodings of satisfiable Boolean formulae in conjunctive normal form.

   Algorithm

      1) Check to see if input w is a CNF Boolean formula (reject if not)
	 and count number of variables n
	 (polynomial time)

	 Second tape now contains the string $I^n, (as many Is as the formula
	 has variables).

      2) Nondeterministic phase
	 M writes a sequence of n T and F over the Is.
	 Different paths of M try all different sequences of values.

	 detal(q,I) = (q,T,R)
	 delta(q,I) = (q,F,R)
	 delta(q,B) = (q,B,S)

	 State q' continues the computation

      3) Deterministic
	 M interprets string using second tape as a truth assignment
	 In pollynomial time accepts or rejects formula


      This algorithm takes polynomial time because each separate path
      only requires a polynomial number of steps (each path is just VERIFYING
      a possible solution).  Encoding a deterministic algorithm to generate
      and verify each path would require an exponential number of steps.


   NP Problems are "polynomially veriable" problems.


* TSP in NP

   A nondeterministic TM M nondeterministically generates all sequences.
   M deterministically verifies if a sequence has total length <= k.


* EXP

   A Turing Machine M is "exponentially bounded" if the machine always halts
   after at most an exponential number of steps.

   If L in NP, then L in EXP


* Certificates

   NP algorithms

      1) nondeterministically generate a string representing a possible solution
      2) deterministically verify whether string is a solution

   If the input is in the language, then at least one appropriate string exists.

   A solution string is a "certificate" or a "witness".
   All and only problems in NP have certificates.

   A solution string must be of length that is polynomial in the length of the
   input - otherwise, you may not be able to deterministically verify the
   solution in polynomial time.

   For SAT, verification is testing whether truth assignments satisfies formula.
   For TSF, verification is testing whether total length is <= k.


* NP-Complete problems

   NP-Complete problems are a special class of NP problems.
   All NP problems can be reduced to any NP-complete problem in polynomial time.

   If we assume that P is not equal to NP, then all NP-complete problems
   are not in P.

   If any one NP-complete problem can be solved in polynomial time, then
   all problems in NP can be solved in polynomial time (P = NP).


   Hamiltonian Cycle is an NP complete problem.
   If we can decide HC in polynomial time, then we can solve every problem
   in polynomial time.

   If NP - P turns out to be nonempty, then HC in NP - P.

   The NP complete languages are the "hardest" languages in NP.


* Why study NP Complete Problems?

   Show cartoons


* How show that a problem is NP-Complete?

   A language L is NP-complete if

      1) L in NP, and
      2) L' is polynomial-time reducible to L for every L' in NP

   If a language L satisfies property 2 but not necessarily property 1, then
   L is "NP-hard".

   The set "NPC" is the set of NP-complete languages.


* Reducibility

   A problem Q can be reduced to another problem Q' if any instance of Q can be
   "easily rephrased" as an instance of Q'.  The solution of Q' thus provides a
   solution to the instance of Q.

   If L' can be reduced in polynomial time to L (a TM M can compute a function
   from instances of L' to instances of L in polynomial time), the L is
   "polynomial-time reducible" to L.



                                        Algorithm for A
                 +------------------------------------+
                 |	                              |
                 |                                  +-|->"yes"
                 |                                 /  |
                 |   +-----+              +-------+   |
             x --|-->| f   |---> f(x) --->| Alg B |   |
   Instance of A |   +-----+Instance of B +-------+   |
                 |                                 \  |
                 |                                  +--->"no"
                 |	                              |
                 +------------------------------------+



 
   This reduction shows that B is at least as hard as A.
   If B is efficiently solvable, then so as A.
   If A requires exponential time, then so does B.