Lecture Notes CMSC 251 1 4 j 88 2 0 104 0 4 5 A1 3 84 0 6 A2 p1 2 48 120 1 p0 158 3 4 m i j i 2 1 1 s i j 2 3 3 2 i 3 4 0 2 A3 p2 3 j 1 3 3 7 A4 p3 Final order 1 2 p4 A1 A2 A3 A4 Figure 34 Chain Matrix Multiplication In the figure below we show an example This algorithm is tricky so it would be a good idea to trace through this example and the one given in the text The initial set of dimensions are h5 4 6 2 7i meaning that we are multiplying A1 5 4 times A2 4 6 times A3 6 2 times A4 2 7 The optimal sequence is A1 A2 A3 A4 Lecture 27 NP Completeness General Introduction Tuesday May 5 1998 Read Chapt 36 up through section 36 4 Easy and Hard Problems At this point of the semester hopefully you have learned a few things of what it means for an algorithm to be efficient and how to design algorithms and determine their efficiency asymptotically All of this is fine if it helps you discover an acceptably efficient algorithm to solve your problem The question that often arises in practice is that you have tried every trick in the book and still your best algorithm is not fast enough Although your algorithm can solve small problems reasonably efficiently e g n 20 the really large applications that you want to solve e g n 100 your algorithm does not terminate quickly enough When you analyze its running time you realize that n it is running in exponential time perhaps n n or 2n or 2 2 or n or worse Towards the end of the 60 s and in the eary 70 s there were great strides made in finding efficient solutions to many combinatorial problems But at the same time there was also a growing list of problems for which there seemed to be no known efficient algorithmic solutions The best solutions known for these problems required exponential time People began to wonder whether there was some unknown paradigm that would lead to a solution to these problems or perhaps some proof that these problems are inherently hard to solve and no algorithmic solutions exist that run under exponential time Around this time a remarkable discovery was made It turns out that many of these hard problems were interrelated in the sense that if you could solve any one of them in polynomial time then you could solve all of them in polynomial time The next couple of lectures we will discuss some of these problems and introduce the notion of P NP and NP completeness Polynomial Time We need some way to separate the class of efficiently solvable problems from inefficiently solvable problems We will do this by considering problems that can be solved in polynomial time 82 Lecture Notes CMSC 251 We have measured the running time of algorithms using worst case complexity as a function of n the size of the input We have defined input size variously for different problems but the bottom line is the number of bits or bytes that it takes to represent the input using any reasonably efficient encoding By a reasonably efficient encoding we assume that there is not some significantly shorter way of providing the same information For example you could write numbers in unary notation 111111111 1002 8 rather than binary but that would be unacceptably inefficient We have also assumed that operations on numbers can be performed in constant time From now on we should be more careful and assume that arithmetic operations require at least as much time as there are bits of precision in the numbers being stored Up until now all the algorithms we have seen have had the property that their worst case running times are bounded above by some polynomial in the input size n A polynomial time algorithm is any algorithm that runs in time O nk where k is some constant that is independent of n A problem is said to be solvable in polynomial time if there is a polynomial time algorithm that solves it Some functions that do not look like polynomials but are For example a running time of O n log n does not look like a polynomial but it is bounded above by a the polynomial O n2 so it is considered to be in polynomial time On the other hand some functions that do look like polynomials are not For example a running time of O nk is not considered in polynomial time if k is an input parameter that could vary as a function of n The important constraint is that the exponent in a polynomial function must be a constant that is independent of n Decision Problems Many of the problems that we have discussed involve optimization of one form or another find the shortest path find the minimum cost spanning tree find the knapsack packing of greatest value For rather technical reasons most NP complete problems that we will discuss will be phrased as decision problems A problem is called a decision problem if its output is a simple yes or no or you may think of this as True False 0 1 accept reject We will phrase many optimization problems in terms of decision problems For example rather than asking what is the minimum number of colors needed to color a graph instead we would phrase this as a decision problem Given a graph G and an integer k is it possible to color G with k colors Of course if you could answer this decision problem then you could determine the minimum number of colors by trying all possible values of k or if you were more clever you would do a binary search on k One historical artifact of NP completeness is that problems are stated in terms of language recognition problems This is because the theory of NP completeness grew out of automata and formal language theory We will not be taking this approach but you should be aware that if you look in the book it will often describe NP complete problems as languages Definition Define P to be the set of all decision problems that can be solved in polynomial time NP and Polynomial Time Verification Before talking about the class of NP complete problems it is important to introduce the notion of a verification algorithm Many language recognition problems that may be very hard to solve but they have the property that it is easy to verify whether its answer is correct Consider the following problem called the undirected Hamiltonian cycle problem UHC Given an undirected graph G does G have a cycle that visits every vertex exactly once An interesting aspect of this problems is that if the graph did contain a Hamiltonian cycle then it would be easy for someone to convince you that it did They would simply say the cycle is hv3 v7 v1 v13 i We could …