Class Note for CMPSCI 601 at UMass(13)
Class Note for CMPSCI 601 at UMass(13)
Popular in Course
Popular in Department
This 15 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 11 views.
Reviews for Class Note for CMPSCI 601 at UMass(13)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
CMPSCI611 NP Completeness Lecture 16 We re going to spend the next few lectures studying a set of computational problems called the NPcomplete problems The essential facts are these 0 Any NPcomplete problem can be solved by a simple but exponentially slow algorithm 0 We don t have polynomialtime solutions to any NP complete problem 0 We can prove that either all NPcomplete solutions have polynomialtime solutions or none of them do 0 It is generally believed that none of them do But proving this would require solving the P versus NP problem one of the best known unsolved problems in mathematics much less theoretical computer sci ence In this lecture we ll go over the basic de nitions and results of the theory of NPcompleteness In the next two lectures we ll see examples of NPcomplete prob lems and how to prove that they are NPcomplete This material has considerable overlap with that of CMPSCI 601 but we ll try here to present things from a more al gorithmic perspective Let s rst review what we mean by a problem The a1 gorithms we ve seen so far in the course have addressed several different kinds of problems 0 Decision Problems The input is some piece of data without loss of generality a string and the output is a bit A decision problem de nes a formal lan guage the set of strings for which the desired output is true For example we might input an undirected graph and output whether it has a perfect matching 0 Search Problems Here the desired output is some piece of data related to the input Often we have more than one acceptable output string For example we might input an undirected graph and output a perfect matching in the graph if one exists 0 Optimization Problems We have an input a set of possible options related to it and a reward function on those options The output is an option that maxi mizes the possible reward for the input If we want to minimize the score we call it a cost function 0 Approximation Problems These are like optimiza tion problems but we are satis ed with an option that gets close to the maximum reward or minimum cost rather than the absolute best option 2 Here are two problem domains where we can de ne each of these four kinds of problems A boolean formula is an expression where the atomic el ements are boolean constants and input variables and the operators are AND A OR V and NOT A boolean formula is said to be in conjunctive normal form CNF if it is the AND of zero or more clauses and each clause is the OR of zero or more literals where a literal is an input variable or a negated input variable For example the formula 121 V I2 V I L 3 1 4 ml 1 V 534 is in CNF It has three clauses and the clauses have three one and two literals respectively A boolean formula has a truth value that depends on the truth values of its inputs The formula is satis able if there is at least one setting of the inputs that makes it true This means that the negation of the formula is not a tautology The decision problem SAT is to input a boolean formula and decide whether it is satis able The decision prob lem CNFSAT is the same but requires that the input is in CNF The decision problem 3SAT is the same but re quires that the input be in CNF with at most three vari ables per clause Given a boolean formula a natural search problem is to nd a satisfying assignment if one exists If we had a decision procedure for SAT we could use it to solve the search problem as follows 0 Test the input formula for satis ability 0 Substitute a constant 0 for 1 in the formula and test it again If it is still satis able set 1 to 0 otherwise set 1 to l 0 With x1 set this way try substituting 0 for 2 If the formula is still satis able set 2 to 0 otherwise set 2 to l 0 Continue in this way setting each variable to a con stant in a way that keeps the formula satis able c When all the variables are set return the setting If the decision procedure runs in time tn the search procedure runs in Ontn 712 4 A natural optimization version of CNFSAT or 3SAT is to input the formula and nd a setting that satis es makes true as many clauses as possible These prob lems are called MAXSAT and MAXSSAT respectively In terms of polynomial or notpolynomial the search and decision problems are also of equal di iculty as we ll see later Our second problem domain is graph colorability Given an undirected graph a valid vertex coloring is an assign ment of a color to each vertex such that there is no edge whose two endpoints are the same color The graph col oring problem is to input graph and nd a coloring that uses as few colors as possible This is closely related to the map coloring problem most familiar from the theorem that every planar map can be colored with four colors Again we have multiple versions of the problem 0 Decision Given G and 19 does G have a kcoloring 0 Search Given G and 19 nd a kcoloring if one ex ists 0 Optimization Given G nd a coloring with as few colors as possible 0 Approximation Given G nd a coloring that uses close to the minimum number of colors 5 Once again if we had polynomialtime solutions to any of the decision search or optimization problems we could nd polynomial time solutions to the others 0 The search problem immediately answers the deci sion problem 0 The optimization problem also solves the decision prob lem 0 Given a search procedure we can use binary search to nd the optimal k and then nd a kcoloring c To solve the search problem as we did for satis abil ity we need a decision procedure that tells us whether a partial kcoloring can be extended to a complete one There is a simple trick to convert a partialcoloring decision problem into an equivalent ordinary decision problem To study whether a problem is solvable in polynomial time then it usually suf ces to look at the simplest case that of decision problems We therefore de ne the class P to be the set of decision problems for which there ex ists an algorithm solving them in 0nk time for some constant k As we discussed in the rst lecture P is a potentially problematic de nition for quickly solvable problems But if we could show a problem to not be in P we would show at least that its running time does not scale with in creasing input size And P has the advantage that it is robust across models several different ways of formal izing algorithm and running time give us the same class We re now ready to de ne NPcompleteness The rst step is to de ne NP a class of decision problems De nition A formal language A is in NP if there eXists another language B in P such that for any string 1 1 is in A iff there exists a string 3 with lyl m0 such that 1y is in B An equivalent more algorithmic de nition of NP is as follows An NPprocedure consists of a guess phase and a veri cation phase Given an input 1 the guess phase chooses an arbitrary string 3 such that lyl MO The veri cation phase is an algorithm that takes both 1 and y as input and returns a bit We say that 1 is in the language of the NPprocedure iff it is possible for the procedure to guess a 3 making the veri cation phase out put true The two de nitions are equivalent because if 3 exists it is possible for the guess procedure to guess it and vice versa Earlier we mentioned the idea of randomly guessing a string this gives us a Monte Carlo algo rithm for any NP language But the success probability of this Monte Carlo algorithm could be very small If there is exactly one 3 such that the veri cation phase ac cepts 1 y the probability of guessing it is TWO This probability is too small for ampli cation to be useful There is an obvious deterministic decision procedure for any NP language simply cycle through all possible strings y and see whether the veri cation procedure accepts 1 y The problem is that there are TOW possible y s of course Our question is whether there is a better way to decide membership in the NP language one that might run in polynomial time Note that proving a language to be in NP is generally simple We need to de ne a string to be guessed and de ne a polytime veri cation procedure that accepts the input and a guess iff the guess proves that the input is in the language For SAT our guess is a setting of the n in put variables and the veri cation procedure evaluates the input formula with that setting For 3COLOR the guess is a threecoloring of the vertices and the veri cation pro cedure checks every edge and accepts if all of them have endpoints of two different colors The class NP includes all the languages in P of course because we can have an NP procedure with no guess phase that just tests for membership in the veri cation phase We need to determine relationships among the languages in NP using the notion of reduction Above we argued for example that if the decision problem SAT were in P so would be the corresponding search prob lem We did this by describing an algorithm for the search problem that would run in polynomial time if it were allowed to make calls to a hypothetical polytime algo rithm for the decision problem This is called a Cook reduction For de ning NPcompleteness though we will need a slightly different notion of reduction Let A and B be two formal languages possibly over dif ferent alphabets A Karp reduction from A to B is a polytime computable function f such that for any string 1 1 E A if and only if f E B If such a reduction ex ists we say that A is polytime reducible to B and write A gp B We also sometimes read this as A is no harder than B The key point of this de nition is that if B is in P and A g B we can be sure that A E P as well This is because we can decide whether 1 is in A in polytime by 0 Computing f x 0 Testing whether f E B and 0 Reporting that answer as our answer for whether 1 E A This is a polytime decision procedure for A because f is assumed to be polytime computable which means not only that the rst step takes polytime but also that the string f has a length polynomial in that of x So the time of the second step is polynomial in the length of f because B has a polytime decision procedure and this is polynomial in the length of 1 because a polynomial of a polynomial is just another polynomial 10 The relation gp is a preorder on the languages in NP be cause it is re exive and transitive It is not antisymmetric because it is possible that both A 3 B and B 3 A are true in this case we say that A and B are polytime equivalent Then 3p is a partial order on the equivalence classes of this relation With the exceptions of 0 and 2 all P languages are poly time equivalent to each other Since P NP might be true it might be that there is only one nontrivial equiv alence class in NP But if P y NP as is generally be lieved there is another important equivalence class De nition A language B is NPcomplete if 1 it is in NP and 2 for any language A in NP A 3p B Thus the NPcomplete languages if they exist are the hardest languages in NP It should be easy to see that they form an equivalence class and that if any NPcomplete language is also in P it follows that P NP ll If a language is NPcomplete then we have strong evi dence that it is not in P We can use the NPcompleteness of a language to talk about nondecision problems even though by de nition these cannot be NPcomplete De nition A problem X with boolean output or other wise is said to be NPhard if there is a Cook reduction from X to some NPcomplete problem B That is there is a polytime algorithm with access to a hypothetical polytime algorithm for X that decides B It should be clear that if X is NPhard and there actually is a polytime algorithm for X then P NP Our general methodology will be to develop a library of NPcomplete problems Once we have one problem there is a straightforward way to get more Lemma Let B be an NPcomplete language and A be a language If we prove OAENP ongl then we may conclude that A is NPcomplete 12 But how do we start this process In CMPSCI 601 we prove the CookLevin Theorem that the language SAT is NPcomplete That proof goes further into the details of the model of computation than we want to go here so we will take its result on faith But if we do that the con cept of NPcompleteness becomes somewhat mysterious why should there be any NPcomplete languages at all In the rest of this lecture we ll give an unconditional proof that a particular language is NPcomplete We ll still need the CookLevin Theorem because SAT is a much more convenient starting place to build up a library of NPcomplete languages The discovery that there are interesting NPhard problems that people really wanted to solve is what made the theory applicable this was the great achievement of Karp To de ne our NPcomplete language we need to x a model of computation that includes NP procedures If Z is an NPprocedure we need there to be a string 2 that indicates given an input 51 how long a string 3 should be guessed by Z and what the veri cation procedure of Z will do given a certain number of steps to run 13 Our language U will be the set of tuples z 51 lg lt such that if 2 denotes the NP procedure Z in this way there is a string 3 of length 9 such that the veri cation phase of Z accepts 1 y in at most 75 steps The inputs 9 and t are given in unary so that the running time of the procedure will be only polynomial in the size of the input to U Theorem U is NPcomplete Proof We rst must show that U is in NP We de ne an NPprocedure that on input 2 x lg lt guesses a string 3 of length 9 and then runs the veri cation phase of Z for up to 75 steps on 1 3 If this accepts we accept the input tuple Otherwise it rejects it runs out of time or 2 isn t valid we reject Clearly it is possible for this procedure to accept z 51 lg ll iffit is in U 14 Now let A be an arbitrary language in NP We will show A 3p U There must exist a string a denoting an NP procedure for A where on an input of length n the pro cedure will guess a string of length at most pn and run for at most qn steps where p and q are polynomials We need a function f such that for any string 51 1 E A iff f E U To do this we de ne f to be the tuple a 51 lpllml 14 This is easy to compute if a p and q are known and takes around 71 1901 qn time to write down the answer a polynomial in the input size 71 By the de nition of U and A this f is in U iff 1 E A Next time we ll see several examples of NPcompleteness proofs starting from the CookLevin Theorem about SAT 15
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'