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.