Design& Analysis of Algorithms
Design& Analysis of Algorithms CPSC 365
Popular in Course
Popular in ComputerScienence
This 18 page Class Notes was uploaded by Ms. Leora Smitham on Thursday October 29, 2015. The Class Notes belongs to CPSC 365 at Yale University taught by Staff in Fall. Since its upload, it has received 12 views. For similar materials see /class/231021/cpsc-365-yale-university in ComputerScienence at Yale University.
Reviews for Design& Analysis of Algorithms
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/29/15
Economics and Computation ECON 425563 and CPSC 455555 Professor Dirk Bergemann and Professor Joan Feigenbaum Lecture IV In case of any questions and or remarks on these lecture notes please contact Oliver Bunn at oliverbunnatyaleedu Economics and Computation Fall 2008 Lecture IV 1 1 Introduction to the Theory of Computation The theory of computation pursues the following goals 0 Formulate mathematical models of 77computation o Formally address issues such as i What is or is not computable What is 77ef cient computation Ef cient computational solutions7 or 77algorithms 7 for problems of interest 7 Proofs that there are no ef cient algorithms for some problems of interest including some for which there are inef cient algorithms 7 Proofs that two problems are 77equivalent77 in computational dif culty or that one problem is harder than the other The theory of computation was initiated by Alan Turing7 Tur36a and Tur36b The fas cinating and ultimately tragic life of Turing is chronicled brilliantly in the play 77 Breaking the Code 7 Whi ln 19367 the date of Turing7s seminal papers7 there were no actual computers7 and so Turing was not concerned with ef ciency Formal treatment of ef cient computation was initiated by Juris Hartmanis and Richard Stearns7 H865 The 77Nobel Prize of Computer Science77 is the Turing Award7 which Hartmanis and Stearns won for their paper HS651 11 Administrative Information Yale courses on the basics of computational theory are 0 CPSC 365 o CPSC 468568 Standard introductory textbooks that deal with computational theory are 0 Cormen7 Leiserson and Rivest Introduction to Algorithms7 CLR01 0 Carey and Johnson Computers and Intractability A Guide to the Theory of NPCompleteness7 GJ79 1Turing Award winners7 names are in red throughout these notes Economics and Computation Fall 2008 Lecture IV 2 2 Computational Complexity 21 Building Blocks A computational problem is a precise statement of a general question to be answered7 usually possessing several parameters or free variables One speci es a problem by giving 0 precise descriptions of all parameters 0 a precise statement of the properties that a solution must satisfy An instance of the problem is obtained by specifying particular values for all parameters Example 1 Traveling Salesman Problem TSP The parameters are 0 a nite set c1L7 cm of cities 0 the distance dcicj E R3 between city cl and city cj for each pair of cities clcj A solution is an ordering or tour 741 cwmgt that minimizes mil d0 i70 i1 d07rm707r17 H l where 7139 17 a 17 is a bijective one to one and onto mapping As an example consider the following instance that will be called gtk for further reference Economics and Computation Fall 2008 Lecture IV 3 In instance gtk of the TSP the tour lt6162C463gt edges of which are labeled in red has length 27 and is a solution ie an optimal or minimum length tour Note that there are TSP instances on in cities for any in 2 2 The fact that a problem is de ned on an in nite family of instances is crucial to computational theory An al gorithm that solves a problem is a stepby step procedure that for any instance is guaranteed to produce a solution In this course it will suf ce to think of an algorithm as a program in a standard pro gramming language such as Java or C and of 77steps as native commands in that language In fact we will usually describe algorithms in even higher level notation than that and count as 77steps instructions that correspond intuitively to atomic operations on a computer eg reading or writing a memory location performing an arithmetic or logical operation sending a packet across a network link etc These components of a computational model can be made completely formal with the notion of a Turing machine model2 lnstances are encoded as nite strings of symbols from a nite alphabet For example 2See Appendix A for a de nition of the Turingmachine modeli Economics and Computation Fall 2008 Lecture IV 4 one can encode TSP instances as strings over the alphabet 07 l7l7707 17137475767189 The encoding instance of instance gtk would then be c1c2C3C41059693 22 Computational Complexity The length or size of an instance is the number n of symbols needed to encode it lntu itively we expect an algorithm to spend more computational resources on larger instances of a problem than on smaller instances The following two natural measures capture the computational complexity of a problem 0 77 Time Complexity77 Tn Tn denotes the maximum number of steps needed to solve an instance of length n 0 77Space Complexity77 Sn Sn denotes the maximum number of memory cells needed to solve an instance of length n One may also consider some less traditional measures eg bandwidth consumed during a distributed computation over a network De nition 1 A problem is called polynomialtime solvable i it can be solved in time for some c E N In the following conjunctive normal form formulas exact de nition below will be pre sented as a structure to examine the concept of time complexity in more detail 221 Conjunctive Normal Form Formulas CNF Let 1 be a set of Boolean variables ie variables that can take the values T or F true or false A literal is either a variable x or its negation z A clause Cj is a disjunction of literals eg 1 V x17 V zgo A Conjunctiue normal form CNF formula is a conjunction of clauses eg C1 Cg where C1 fg V x5 and Cg 1 V 3 V f4 An assignment 61 Em of truth values to the variables 1xm in a CNF formula C is a satisfying assignment if Cel Em evaluates to T For example T F T T T is a satisfying assignment of C1 Cg above but T T F T F is not Economics and Computation Fall 2008 Lecture IV 5 Example 2 Veri cation of Satis ability An instance is a pair QQ where C is a CNF formula on m variables with h clauses and 5 61 em is an assignment to the variables ofC The solution is yes if is a satisfying assignment ofC and no otherwise Observe that one is given a formula and an assignment So example 2 is solely about determining a truefalse statement To see why this problem is solvable in polynomial time observe that under a reasonable encoding the length of an instance is at least proportional to m h and at most propor tional to ink the former applies if all clauses are short and the latter if they are long On the other hand the formula can be evaluated at by a program that performs 0mh logical operations De nition 2 The Class P The class of yesno or decision problems that are solvable in polynomial time is denoted by P Instead of the veri cation from Example 2 one might also be interested in ndingdetermining a satisfying assignment if one is given a ONF This is captured by the following example Example 3 Solving for Assignment in SAT Search Version of SAT An instance of this problem is a CNF formula C on Boolean variables 1zm A solution is a sat isfying assignment 61 6m ofC if one ecoists Observe that in this case an assignment is no longer part of the input but part of the solution Instead of simply deciding whether a particular assignment is true or false a satisfying assignment needs to be determined If a solution to Example 3 is found then one can use the logic as outlined in the sequel of Example 2 to quickly verify a solution This leads to the following de nition De nition 3 I 1 f V r a tim problems are those for which eor reet solutions if they CCElSt can be veri ed in polynomial time Hence nondeterministic polynomial time problems are solely characterized by the ef ciency of the veri cation of their solution Note that the search version of the satis ability problem is a partial relation on the set of ONE formulas in that it is not de ned on unsatis able formulas ie those formulas Cx1m on which all assignments evaluate to Hence it is natural to consider the following example that considers the 77decision version77 of the satis ability problem Economics and Computation Fall 2008 Lecture IV 6 Example 4 Decision Version of SAT Here an instance is once again a CNF for mula C but a solution is simply yes ifC is satis able is if 3 C3 T and n0 ifC is unsatis able An important technique in the study of computational complexity is reducing search to decision In the context of the satis ability problem this means that if there were a polynomial time algorithm for the problem in Example 4 there would be one for the problem in Example 3 To see this note that if Czl m is a CNF formula on m Boolean variables then both CiT1 T m and CLF1 F are CNF formulae on m 71 variables Both can be computed quickly by 77plugging in77 the appropriate truth value for the Boolean variable x and 77simplifying the result For example if C123 1 V 2 V f3 A 1 V 2 V f3 A 1 V 2 V 3 then CLT 2 V f3 A 2 V 3 and CLF 2 V f3 Let 77decide sat77 be an algorithm that takes as input a CNF formula outputs 77yes77 if the input is satis able and outputs 77nd7 otherwise Observe that the following algorithm which uses 77decide sat77 as a subroutine solves the search version of the satis ability problem Economics and Computation Fall 2008 Lecture IV 7 find 7 satC KI H C for 239 e 1 to m if decide satIT yes e lt T 1 lt 1LT else if decide satIF yes e lt F 1 lt else OUTPUTUC is unsatis able OUTPUT61 em To see that this reduction of 77 nd sat77 to 77decide sat77 is correct note that if C is satis able one or both of the following statements must be true 0 77C has a satisfying assignment in which 1 T and CLT is also satis able7 o 77C has a satisfying assignment in which 1 F and CLF is also satis able7 In the rst execution of the for loop in 77 nd sat one discovers whether both of these statements are false if they are the algorithm terminates and declares C to be unsatis able If at least one of these statements is true the algorithm records the rst bit of a satisfying assignment and proceeds on a formula on m 7 1 variables lterations 2 through m of the for loop perform the analogous computation for variables x2 through zm To see that this is a polynomialtime reduction note that the size n of input C is greater than m 77 nd sat77 makes at most 2m lt 271 calls to 77decision sat Thus if 77decision sat ran in time3 00 77 nd sat77 would run in time 0010 3Note that this hypothesis is believed to be false ie it is not expected that the problem of Example 4 is in P Economics and Computation Fall 2008 Lecture IV 8 23 The Class NP The notion of nondeterministic polynomial time see De nition 3 can now be eshed out to yield a formal de nition of the class NP Recall that a computational problem is characterized by a set of X of instances and a set Y of solutions We generalize our earlier notion of computational problem by allowing for the possibility that some instances have no solutions Let and denote the sizes of strings a E X and y E Y De nition 4 The Class NP The class NP of nondeterministic polynomial time decision problems are those in which the sets X and Y have the following properties 0 There is a polynomialp such that w lt pmzl wheneuery is a solution to the instance z o The decision problem is y a solution to the instance z is in P The set of yes instances 7 ie the set of all z for which there exists at least one solution y is called an NP set or an NP language The corresponding NP search problem is given an instance x nd a solution y if one exists The language SAT of satis able CNF formulas is a canonical NP set Example 1 gives an optimization version of the TSP The TSP can be formulated as a nondeterminis tic polynomial time decision problem An instance of this decision problem is a triple CdK7 where C is a set of cities and d a distance function as before7 and K is a positive7 real number Qd7 K is a yes instance if there exists a tour of Cd that has total length at most K The corresponding search problem is given an instance 07 d7 K7 nd a tour of Cd that has total length at most K if one exists Central to the study of computational complexity is the notion of an NPcomplete set De nition 5 NPcompleteness The set S is NPoomplete i it is in NP and is a hardest set in N in the following sense For any set T E NP there is a polynomial time computable function f such that zETlt fzES Note that the existence of f means that7 if S were in P7 then T would be in P Equiv alently7 if S is NP complete7 and S 6 P7 then P NP The search and optimization Economics and Computation Fall 2008 Lecture IV 9 problems that correspond to an NP complete set S are called NPhard if they can be solved in polynomial time4 then P NP SAT is an NP complete set So is the set of yes instances of TSP described above Lit erally tens of thousands of problems that arise naturally in mathematics science engi neering economics and other elds have been proven to be hard NP hard One of them is the 77 Combinatorial Auction Problem77 that will be studied later in this course NP completeness was rst formulated by Steven Cook 00071 who also showed in the same paper that SAT is NP complete The fact that natural NP complete problems abound was demonstrated shortly thereafter by Richard Karp Kar72 Extraordinary effort has gone into the quest for polynomial time algorithms that solve NP hard problems of practical importance and yet no such algorithm has been found Furthermore it seems intuitively clear that verifying the correctness of a solution should in general be easier than nding a solution in other words it seems clear that P NP Surprisingly no proof of this claim has been found Conjecture 1 Fundamental Conjecture of Computer Science Py NP 24 The Class PSPACE After restricting attention to computational complexity as measured by Tn the last part of this lecture will focus on the concept of space complexity as captured by Analo gous to the de nition of polynomial time solvability the following de nition captures the notion of polynomialspace solvability De nition 6 Polynomialspace solvable problems are those solvable by algorithms whose space eomplem39ty satis es fore E N An enormously important class of examples of polynomial space solvable problems is given by quanti ed Boolean formulas 4This is a question of ongoing interest but computer scientists do not believe that NPhard problems can be solved in polynomial time Economics and Computation Fall 2008 Lecture IV 10 Example 5 Quanti ed Boolean Formula QBF An instance is a quanti ed Boolean formula 11 ie an expression of the form 3z1V23d3Vz43zm1Vzm Cx1m where C is a quanti er free CNF formula A solution is simply yes if 1 is a true quanti ed Boolean formula and no if 1 is false The language of yes instances of this language is denoted by TQBF De nition 7 The Class PSPACE If a decision problem is solvable in polynomial time and L is the set of yes instances of that problem then we say that L E LSPAOE The QBF problem crystallizes two important properties of the complexity class PSPACE and of space bounded computation in general 1 Space is a more powerful computational resource than time in the sense that an algorithm can reuse space but cannot reuse time P There is an intimate relationship between the class PSPACE and games Each QBF instance can be interpreted as a perfect information game between the 77exists player whose goal is to satisfy the formula C and the 77forall77 player whose goal is to falsify C The yes instances of QBF are the games in which the 77exists77 player has a winning strategy These two properties will be outlined separately in the following two parts 241 Space as a Powerful Computational Resource To illustrate the fact that 77space is a more powerful computational resource than time we give a polynomial space algorithm to decide QBF We represent the truth values FT as bits 01 and use the fact that 0 lt 1 Recall the notion of the lexicographic order of the Cartesian product A gtlt B of two totally ordered sets A and B ab lt a b gt a lt a or a a and b lt b Repeated application of this construction imposes a total lexicographic order on 01k for any h For example the lexicographic enumeration of 013 is given by 000 001 010011 100 101 110 111 Economics and Computation Fall 2008 Lecture IV 11 If is a bit string in 01k 7 1k let ma a be the string that follows in the lexico graphic enumeration nextk is unde ned and denoted by some symbol LgZ 0 1 decide 7 QBFT OddBits E 61 63 6m1 OWL2 L1 EvenBits E 62 64 Em OWL2 L2 lf C61626m16m If EvenBits 1W2 OUTPUTYES Else EvenBits nextEvenBits Goto L2 Else lf OddBits 1W2 OUTPUTNO Else OddBits nextOddBits Goto L1 In the outer loop of decide QBF we consider in turn each assignment 6163 6m1 to the existentially quanti ed Boolean variables x13 xm1 In the inner loop we check whether for all possible assignments 62646m to the universally quanti ed variables x24 zm the formula C is true If the inner loop completes successfully for any assign ment 61 63 6m1 we have proven that KI is true and hence we halt and output YES Otherwise we have proven that no assignment has this property and we output NO The crucial point about the space complexity of this procedure is that there is no need to allocate fresh space when the function 77next is called The same bits that were used to store 61 63 6m1 62 64 Em respectively can be re used to store nezt61 63 6m1 next62 64 Em respectively Time cannot be used the same fashion lndeed 77decide Economics and Computation Fall 2008 Lecture IV 12 QBF77 will run for time 92 in the worst case 242 PSPACE and Games The second point crystallized by the QBF problem is the relationship between PSPACE and games Each QBF instance can be interpreted as a perfect information game between the 77exists77 player whose goal is to satisfy the formula C and the 77forall77 player whose goal is to falsify C Here one builds upon the notion of extensive form games which have not been covered in the introductory lectures on game theory In short these games have an additional time component A player can wait and observe the other players action before making a move by herself Clearly this is a generalization of the concept of simultaneous move games in which all players act at the same time The yes instances of QBF are the games in which the 77exists77 player has a winning strategy 5 For example consider the following yes instance KI of QBF 31V233 1 V 2 V 3 A 1 V 2 V f3 5For the clarity of the exposition the term 77strategy77 is used in an informal manner in this context According to the strict economic definition a strategy in an extensiveform like the one displayed below assigns an action to every node in the gametree no matter whether this node is reached or not Economics and Computation Fall 2008 Lecture IV 13 3 moves at the top level V at the second level and nally 3 at the third 3 can create a winning outcome for herself by playing x1 1 combined with x3 0 with the latter play being irrespective of player V7s choice6 This strategy is displayed in red in the above game tree Note that the game tree has size exponential in m and hence cannot be built explicitly during the execution of a polynomial space algorithm The algorithm 77decide QBF shows that we need not build the whole tree We can explore it one branch at a time keeping track of whether we have found a winning strategy for 3 243 PSPACECompleteness of QBF QBF is in fact a PSPACE complete set For any set T E PSPACE there is a polynomial time computable function f such that for all instances z z e Tlt fz e QBF 6There are other choices for player 3 that create a desired outcome for her Economics and Computation Fall 2008 Lecture IV 14 Many other perfect information7 polynomial depth games correspond to PSPACE complete sets as well7 including polynomial depth ngtltn GO and polynomial depth an CHECKERS lndeed7 in a sense that is beyond the scope of this course7 all PSPACE complete sets rep resent games 25 Relationship among Complexity Classes We have the following relationships among complexity classes P Q NP Q PSPAOE Amazingly7 it is not known whether either of these inclusions is proper the seemingly bizarre possibility that P PSPACE has not been ruled out but is7 of course7 believed to be false Economics and Computation Fall 2008 Lecture IV 15 A TuringMachine model of Computation Deterministic k tape Turing machine M There is one read only input tape on top and k 7 1 read write workoutput tapes M is a triple PQ6 that is de ned as follows 0 P is the tape alphabet a nite set of symbols Assume D 77blank77 symbol D 77start77 symbol 0 and 1 are four distinct elements of P 0 Q is the state set a nite set of states that Ms control register can be in Assume qstm and qhalt are two distinct states in Q o 6 is the transition function a nite table that describes the rules or program by which M operates 6Qgtltl kaQgtltPk 1gtltLSRk Economics and Computation Fall 2008 Lecture IV 16 5q7 017 Uk q 7 0 2 H702 217 means that7 if M is in state q7 and the read or readwrite tape heads are pointing at the cells containing 01 quot471 then the following 77step of the computation is performed 7 the readwrite tape symbols 02 0k are replaced by 0 0 tape head 239 moves left7 stays in place or moves right7 depending on whether 21 is in LS or R i the control register state is changed to 1 When M starts its execution on input z 01 70 we have 1 Istm 0 input tape D 0 all other tapes lb Meaning of qhalt 6qhalt7 017 W700 ghaim 027 7Uk7Sk W017 mm Designate one of the readwrite tapes as 77the output tape Turing machine M 77 computes the function f 7 if for all z E F the execution of M on input z eventually reaches the state qhalt and when it does7 the contents of Ms output tape is M 77runs in time T77 if for all n and all z E P M halts after at most Tn steps Economics and Computation Fall 2008 Lecture IV References CLROl Coo71 cum H865 Kar72 Tur36a Tur36b Whi TH Oormen OE Leiseron and RL Rivest Introduction to Algorithms MIT Press and McGraw Hill 2nd edition 2001 1st Edition published in 1990 SA Cook The complexity of theorem proving procedures Proceedings of the Third Symposium on the Theory ofC r t39 g A 39 quot ofC r t39 3 Ma chinery pages 1517158 1971 MR Carey and DS Johnson Computers and Intractability A Guide to the Theory of NP Completeness Freeman 1979 J Hartmanis and R Stearns On the computational complexity of algorithms Transactions of the MAerican Mathematical Society 1172857306 1965 RM Karp Reducibility among Combinatorial Problems in Miller and Thatcher eds Complepity of Computer Computations Plenum 1972 pp 85 103 Entschei Series 2 A Turing On computable numbers with an application to the dungsproblem Proceedings of the London Mathematical Society 422307265 1936 article lll Entschei Series 2 A Turing On computable numbers with an application to the dungsproblem Proceedings of the London Mathematical Society 435447546 1936 article 1111 H Whitmore Breaking the code First performed in London7s West End in 1986 and New York City7s Broadway in 1987 both times with Derek Jacobi playing the part of Alan Turing