November 19

* P

  P is the class of all polynomially decidable languages

  Theorem:  P is closed under complement.
  If TM M decides L, then the complement of L is decided by the
  version of M that inverts y and n (polynomial bound unaffected).


* We define complexity as a function of input length
  (worst case amount of time used over all inputs of a given length).

  The following code executes on the order of n instructions, and is thus said
  to have time complexity O(n):

     for i = 1 to n do
	val = val*2;

  The following code is O(n) because the constant (the increase of 2 in number
  of operations) is ignored:

  for i = 1 to n do
     val1 = val1*2;
     val2 = val2*2;
     val3 = val3*2;

  In contrast, the following code has time complexity O(n^2):

  for i = 1 to n do
     for j = 1 to n do
	val = val*2;


  For TM, the complexity of:
     TIME = #transitions before halting
     SPACE = #cells used during computation


* Show exponential growth charts


     A "tractable" problem is a problem that is in P.

     Although polynomial problems could be expensive (n^100), typically
	polynomial time problems are low-order polynomial time

     This distinction is useful because there are many problems which NOBODY
     has found a polynomial algorithm to compute.


* Argument:  this only categorizes algorithms on worst-case performance
  Better argument, though much more difficult, is average-case analysis
  Phase transition

  Average-case analysis difficult because we don't know distribution of input

  P still useful as a first step, provides a good classification

  All regular languages and all context-free languages are in P
  (DFAs require only |w| time, and deciding if w in CFL takes only
  polynomial time).


* Problems vs. languages



   Many problems ask for an output value to be computed
   (search the space of possible solutions for an optimal answer)

   A decision problem is a yes/no version of a search problem such that the
   ability to solve a search problem => the ability to solve a decision
   problem (many times the converse is true as well).


   Example

      Search Problem:  Input = G, a CFG
	 Desired Output = shortest w such that w has to leftmost derivations
	    (if G is ambiguous) or "not ambiguous" if G is unambiguous

      Decision Problem:  Input = G, a CFG
	 Desired Output = "yes" if G is ambiguous
			  "no" if G is unambiguous


   In general we have taken a search problem and perhaps made it easier by
   replacing it with a decision problem.  If the easier problem cannot be
   solved in polynomially time, certainly the harder problem cannot be solved
   in polynomial time.


* Some well-known problems

   - Traveling Salesman Problem


      Search Problem:  Given a complete graph with weights on the edges, find a
	 cycle of least total weight that visits each vertex exactly once.

      Decision Problem:  TSP = {, k:  G is a complete graph with weights on
	 edges that contains a cycle of total weight <= k visiting each vertex
	 exactly once}



	     *
            /|\
        10 / | \ 5
          /  |9 \
         / 6 |   \
        *----|----*
         \   |   /
          \  |  /
         9 \ | / 3
            \|/
	     *


     If the Decision Problem cannot be solved in polynomial time, the Search
     Problem cannot be solved in polynomial time.

     No known polynomial-time algorithm for TSP


   - Reachability

     Given a directed graph G <= VxV, where V = {v1, ..., vn} is a finite set,
     and two nodes vi, vj in V, is there a path from vi to vj?

     Is Reachability in P?

     Decision Problem:  {:  G contains a path from vi to vj}

     Reachability can be solved in in polynomial time.

	Compute reflexive transitive closure of G in time O(n^3) by TM
	This is shown in book
	The reflexive transitive closure will shown if path from vi to vj.


     Reachability is in P.


   - Eulerian Cycles

     Given a graph G, is there a closed path in G (first and last vertices are
     the same) that uses each edge exactly once?

     Given background on bridges

     The path can visit each node many times of not at all if node disconnected.
     A graph that contains such a path is a Eulerian graph.


     G1 = ({v1,v2,v3,v4}, {(v1 v3), (v1 v4), (v2 v1), (v2 v3),
			   (v3 v1), (v3 v2), (v4 v2), (v4 v3)}
	
     G2 = ({v1,v2,v3,v4,v5,v6,v7}, {(v1 v2), (v2 v3), (v3 v4), (v4 v5), (v5 v6),
				    (v6 v1), (v1 v7), (v7 v2), (v7 v3), (v7 v4),
				    (v7 v5), (v7 v6)}

     G1 contains a Euler Cycle (v1, v3, v1, v4, v3, v4, v2, v3, v2, v1) and
     G2 does not contain any Euler Cycles.

     Decision Problem:  L = {:  G is Eulerian}


     A graph is Eulerian iff
	(a) For any u,v in V (neither is disconnected), there is a path from
	    u to v, and
	(b) All nodes have equal numbers of incoming and outgoing edges.

     Algorithm
	1) Make sure all nodes are connected.
	   Compute reflexive transition closure in O(n^3) time,
	   then test n^2 connections
	2) Test for equality of incoming and outgoing edges in O(n) time.


     The Euler Cycle Problem is in P.

     Notice that we showed the Euler Cycle Problem is in P by using the
     established fact that Reachability is in P.
     We "reduced" the Euler Cycle Problem to an already solved problem.


   - Hamiltonian Cycle

     Given a graph G = (V,E), find a cycle that contains each vertex in V.

     Decision Problem:  HC = {: G is a Hamiltonian graph}.

     How decide the language?
     List all permutations of the vertices
     Check to see if any permutation is a Hamiltonian cycle in the graph.

     There are |V|! permutations of the matrices, thus the algorithm is
     exponential.


   - Boolean Satisfiability

     Given a boolean formula consisting of
	1) boolean variables x1, x2, ...
	2) boolean connectives ^, v, -, -> <->
	3) parentheses

     Determine a "truth assignment" (a set of T/F values for the variables)
     that causes the entire formula to have the value true.
     A truth assignment that evaluation the formula to true is a
     "satisfying assignment".
     A formula that has at least one satisfying assignment is a
     "satisfying fomula".

     Decision Problem:  SAT = {f:  f is a satisfiable boolean formula}.

     f = ((x1 -> x2) v -(--x1 <-> x3) v x4)) ^ -x2

     has the satisfying assignment 
	f = 0->0 v -((-0<->1)v1)) ^ -0
          = (1 v -(1v1)) ^ 1
	  = (1v0) ^ 1
	  = 1

     The formula f thus belongs to SAT.

     SAT does not have any known polynomial-time algorithms



     P  = DTIME = Deterministic Polynomial Time
     NP = NTIME = Nondeterministic Polynomial Time



	   +-----+     Open Question:  Does P = NP?
	  /   NP  \
	 |  +---+  |
	 | /  P  \ |
	 | \     / |
	  \ +---+ /
	   +-----+



     NP is the class of languages that can be verified by a poynomial-time
     algorithm.