Class Notes (783,538)
Canada (480,727)
CS 341 (26)

lecture #9 - NP Completeness
lecture #9 - NP Completeness

45 Pages
Unlock Document

University of Waterloo
Computer Science
CS 341
Forbes Burkowski

NP Completeness Traveling Salesperson Problem (TSP): Given a weighted undirected graph G = (V, E), find a cycle containing every vertex exactly once such that the sum of weights of edges in the cycle is a minimum. A greedy algorithm does not work (see next slide). An exhaustive search will work but takes much too long for even moderate values of n. Exhaustivesearch: Trying each permutation of the cities involves testing (n - 1)! sequences. There is no known polynomial time algorithm that is guaranteed to find the minimal cost tour. There are many polynomial time algorithms to generate approximations to the optimal solution. TSP & Greedy (Near Neighbour) Consider NN solution for rd100 taken from TSPLIB: Start here TSPLIB: 1 Practical vs. Impractical A simple characterization of algorithms: We will consider polynomial time algorithms to be practical or efficient (even with large exponents) Algorithms that require exponential time (or worse) are regarded as impractical. The Question of Efficiency What do we do if we have a problem like TSP that has no polynomial time solution? If we could prove that no polynomial time algorithm can be designed to solve the problem, then we could go about looking for approximate solutions or heuristics with knowing that no practical algorithm exists to find the optimal solution. There is a set (class) of problems thatquire exponential solutions and this can be proven. But there are many other problems (e.g. TSP) for which such a proof is not known despite considerable effort by researchers. 2 So instead we must go for a lesser prize: We prove that the problem is NP-hard. That is: it is essentially equivalent to other problems for which no known polynomial time solution exists. Such a proof does not show that a polynomial time solution does not exist but only that thousands of other experts have never found an efficient solution either. Why is this important? If you have an NP-hard problem you have two choices: 1.You can decide that all the experts have missed some vital point and so you set about looking for a polynomial time solution 2.You decide that you are not likely to do better than the experts and set about looking for an approximation or heuristic algorithm that gives a reasonable solution. Optimization vs. Decision Problems Optimization problems: Find a value, object or configuration that optimizes some function. For example: in TSP we are looking for a least cost tour. Decision problems: The solution of a decision problem is yes or no. Some examples: Is a given number a prime number? In the TSP-D problem we are given a value B and we want to know whether there is a tour with length < B. NP-completeness theory deals with decision problems. D for Decision 3 Observation: If the cost function is easy to evaluate, then the decision problem can be no harder than the corresponding optimization problem. For example: If we can find the minimum length of a TSP tour, then we can compare it to value B and thus solve the decision problem. Often the reverse is also true: If we can solve the decision problem in polynomial time then we can solve the optimization problem in polynomial time as well. Class P (Polynomial) Review: What does running time mean? The running time of an algorithm A is a functAon T (n) where n is the size of the input instance. T (n) = worst case time to solve an instance of size n. A What is the size of an instance? Size = number of bits needed to encode the problem instance. Definition: A decision problem Q belongs to the class of problems P if and only if there exists a polynomial time algorithm solving problem Q. 4
More Less

Related notes for CS 341

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.