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.