Question? Leave a message!




NP Completeness

NP Completeness
ECE 250 Algorithms and Data Structures NP Douglas Wilhelm Harder, M.Math. LEL Completeness Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.NP Completeness 2 Deterministic algorithms An algorithm is deterministic if the sequence of steps taken to solve a given problem by an algorithm is predetermined and linearly ordered The Turing machine we described is deterministic: – For any stateletter pair, there is only one entry in the transition table Other than some of the stochastic algorithms, every algorithm in this course has been deterministicNP Completeness 3 Deterministic polynomialtime algorithms A deterministic polynomialtime algorithm is such an algorithm that solves any problem in polynomial time k – The algorithm is O(n ) for some k ≥ 0 2 – An n ln(n) algorithm runs in polynomial time as n ln(n) = O(n ) We will represent the totality of all problems that can be solved in polynomial time using a deterministic algorithm by the symbol PNP Completeness 4 Deterministic polynomialtime algorithms Consider the travelling salesman problem: In a complete weighed graph, what is the least weight Hamiltonian cycle A deterministic algorithm to find a solution is to do tree traversal – This tries every path – The run time is Q(V) 2 V – The HeldKarp algorithm runs in Q(V 2 ) time • It uses dynamic programming – To the best of our knowledge, this problem is not in PNP Completeness 5 Nondeterministic algorithms A Turing machine is nondeterministic if the transition table can contain more than one entry per stateletter pair – When more than one transition is possible, a nondeterministic Turing machine branches and creating a new sequence of computation for each possible transition With C++, consider a process that at some point spawns a thread or another process destined to run on another core or processorNP Completeness 6 Nondeterministic algorithms A nondeterministic algorithm can be implemented on a deterministic machine in one of three manners: – Assuming execution along any branch ultimately stops, perform a depthfirst traversal by choosing one of the two or more options and if one does not find a solution, continue with the next option – Create a copy of the currently executing process and have each copy work on one of the next possible steps • These can be performed either on separate processors or as multiple processes or threads on a single processor – Randomly choose one of the multiple optionsNP Completeness 7 Nondeterministic polynomialtime algorithms A nondeterministic polynomialtime algorithm is a nondeterministic algorithm that can solve a problem on any input in polynomial timeNP Completeness 8 Nondeterministic polynomialtime algorithms The travelling salesman problem can solved nondeterministically: – At each step, spawn a thread for each possible path – As you finish, compare them and determine the shortest – The run time is now Q(V) – This is a bruteforce searchNP Completeness 9 Nondeterministic polynomialtime algorithms Let’s try a slightly different problem: ―Is there a Hamiltonian cycle of weight no greater than K – This is not an optimization problem – It is a Booleanvalued decision problemNP Completeness 10 Nondeterministic polynomialtime algorithms Currently, we don’t know any deterministic polynomialtime algorithm that can solve either question: ―What is the Hamiltonian cycle of least weight ―Is there a Hamiltonian cycle of weight no greater than K‖ In the second case, however, we only have to find one cycle with weight less than K—we may not have to traverse the entire treeNP Completeness 11 Nondeterministic polynomialtime algorithms Consider the following decision problem: ―Is there a path between vertices a and b with weight no greater than K‖ Dijkstra’s algorithm can answer this in polynomial time – Dijkstra’s algorithm also solves the optimization problemNP Completeness 12 Nondeterministic polynomialtime algorithms On the other hand, the question: ―Is there a Hamiltonian cycle of weight no greater than K‖ seems like it might be easier to solve than ―What is the Hamiltonian cycle of least weightNP Completeness 13 Nondeterministic polynomialtime algorithms Suppose we had an algorithm that could tell us where to look—let’s call such an algorithm an oracle – To answer the question decision question in the affirmative, it is only necessary to find one cycle with weight no greater than K – Suppose this oracle could tell us, in polynomial time, which path to take create the Hamiltonian cycle – We can verify the result in polynomial time by adding up the weights of the edges—an Q(V) operationNP Completeness 14 Nondeterministic polynomialtime algorithms Note that finding the minimumweight Hamiltonian cycle is a much more difficult problem – Even if the oracle found us the path in polynomial time, we cannot confirm that it is the shortest path in polynomial time – We cannot verify the result in polynomial timeNP Completeness 15 Nondeterministic polynomialtime algorithms Thus, we have two classes of problems Decision problem Optimization problem Is there a cycle of length less than K What is the minimum length cycle If the answer is“yes”, an oracle could The oracle could guide us as to the guide us as to the choices we should choices we should make at each non made at each nondeterministic step deterministic step to find the cycle with and at the end, having added the minimum length, but we have no means weights of the edges, we can determine of verifying that this is the shortest cycle that yes, indeed, the oracle has directed without checking all other solutions; us to a solution that answers the that is, we cannot verify the solution in question in the affirmative. polynomial time.NP Completeness 16 NP and NP Hard We will say that both these problems are NP Hard – Solving either one allows us to solve the decision problem Any problem that we 1. Can solve on a nondeterministic machine in polynomial time and 2. Verify on a deterministic machine in polynomial time, will be said to be in the class NP – This includes the decision problem, but not the optimization problem – The class NP also includes P Claim: The traveling salesman decision problem is simultaneously – The easiest NP Hard problem – The most difficult NP problemNP Completeness 17 NP and NP Hard Consider this Venn diagram where P ⊆ NP What is the minimum length Hamiltonian cycle Polynomialtime algorithms Polynomialtime algorithms Exponentialtime algorithms Is there a Hamiltonian cycle of length no greater than KNP Completeness 18 P and NP We know that P ⊆ NP The million dollar question: – For every problem that is in NP, are there algorithms that can solve those problems in polynomial time on a deterministic machine – That is, can we solve the traveling salesman decision problem in polynomial time on a deterministic machine – More succinctly: Is P = NP NP Completeness 19 P and NP Why is it a million dollar question – It is one of seven Millennium Prize Problems posed by the Clay Mathematics Institute – Correct solutions will result in a prize of one million U.S. dollars New Line Cinema http://demonocracy.info/NP Completeness 20 NP problems We will now look at a number of NP problems that have no known deterministic polynomialtime solutions – We have already seen the travelling salesman problem – Boolean satisfiability problem – The knapsack problem – Subset sum problem – Subgraph isomorphism problem – Hamiltonian path problem – Graph coloring problem – Clique problem – Independent set problem – Vertex cover problem – Dominating set problem – Integer programming problemNP Completeness 21 Boolean satisfiability The Boolean satisfiability problem – Given a Boolean expression, is there at least one combination of values of the Boolean variables such that the expression is true p q r pr spqs  – Cook showed that, in a sense, this was the most difficult NP problem in his 1971 paper The Complexity of TheoremProving Procedures – If a polynomialtime deterministic algorithm can solve this problem, then polynomialtime deterministic algorithms can solve all NP problems, including the traveling salesman decision problem Refer to 2.82 from Principia Mathematica by Russell and WhiteheadNP Completeness 22 Knapsack problem The knapsack problem – Suppose a container can hold a maximum weight W – Given a number of items with specified weights and values, is there some combination of items that has a total value greater than or equal to V without exceeding the maximum weight W – The general optimization problem is NP HardNP Completeness 23 Subset sums The subset sum problem – Given a set of integers, is there a combination of those integers that adds to zero –915, –791, –499, –453, –257, –184, –73, 90, 207, 510, 541, 563, 721, 755 –961, –715, –672, –655, –188, –147, –124, 253, 256, 547, 629, 763, 806, 815 –991, –891, –638, –550, –549, –454, –453, –144, 17, 217, 259, 370, 538, 566, 651NP Completeness 24 Subgraph isomorphisms The subgraph isomorphism problem – Given two graphs, is one graph isomorphic to a subgraph of the other – Here, does the left graph have a subset of six vertices and a subset of edges such that it looks the same as the graph on the rightNP Completeness 25 Hamiltonian paths Hamiltonian path problem – Does a graph have a Hamiltonian path • Is there a simple cycle of length VNP Completeness 26 Graph colorings The graph coloring problem – Given a graph and n colors, is it possible to assign one of the colors to each of the vertices so that no adjacent vertices have the same color – Complete graphs requires V colors – Finding the smallest number of colors for a graph is NP HardNP Completeness 27 Cliques The clique (complete subgraph) problem – Does a graph have a clique of size at least n – Given a graph, find the largest clique is NP HardNP Completeness 28 Independent sets The independent set problem – Given a graph, is there a set of n vertices such that no two vertices in that set are adjacent – Finding the largest set of such vertices is NP HardNP Completeness 29 Vertex covers The vertex cover problem – Given a graph, is there a set of n vertices such that every edge is incident with at least one of those vertices – Finding the minimum number of such vertices is NP HardNP Completeness 30 Dominating sets The dominating set problem – Given a graph, is there a set of n vertices such every vertex is adjacent to at least one of the vertices in the set – Finding the smallest set of such vertices is NP HardNP Completeness 31 Integer programming Given an objective function and a set of constraints – Find 0 or 1 values of the variables that satisfy the constraints and maximize the objective function Objective function: v + 2w + 3x + 4y + 2z v + 2w + x ≤ 3 v ≥ 0 2v + 3w + 2y ≤ 6 w ≥ 0 3v + 2w + z ≤ 5 x ≥ 0 Maximum at v = x = y = 1 v + 2x + 2y ≤ 4 y ≥ 0 w = z = 0 3v + 2x + 2z ≤ 6 z ≥ 0 2v + y + 4z ≤ 6 w + 2x + y ≤ 3 Maximum at y = 2 2w + x + z ≤ 3 v = 1 2w + 2y + 2z ≤ 5 w = x = z = 0 x + y + z ≤ 2 – Allowing the variables to take on integer values is NP HardNP Completeness 32 NP problems Question: Suppose that we find a deterministic polynomialtime algorithm to solve one of these problems—does this help us with finding solutions to the other problems To answer this, we must define a reduction of a problem – A reduction is a transformation of one problem A into another problem B such that the solution to B yields a solution to A – A reduction that may be preformed in polynomial time is said to be a polynomial reductionNP Completeness 33 Polynomial reduction Graphically, we may think of the following image: To solve Problem A, we: – Reduce the problem to Problem B in polynomial time – Solve Problem B – Revert the solution back into a solution for Problem ANP Completeness 34 Polynomial reduction For example, to multiply two n digit decimal numbers: – Reduction: convert the two numbers into binary numbers – Multiply the two binary numbers – Reversion: convert the solution back into a decimal number Both the reduction and the reversion run in Q(n) time – If a decision problem is reduced to a decision problem, the corresponding result can be returned in Q(1) timeNP Completeness 35 Polynomial reduction Another example: Does a list have a duplicate element – Reduction: Sort the list – Simpler problem: Does a sorted list have a duplicate element – Reversion: Return true or false, as is Both the reduction and the reversion run in Q(n) time – If a decision problem is reduced to a decision problem, the reversion is therefore Q(1) • Either the solution or its negationNP Completeness 36 Polynomial reduction Can we reduce the Hamiltonian path problem to the travelling salesman problem – Finding a Hamiltonian cycle to finding a cycle in a complete weighted graph with weight less than or equal to KNP Completeness 37 Polynomial reduction Can we reduce the Hamiltonian path problem to the travelling salesman problem – Each edge has weight 1 and include all other edges with weight 2 – Is there a Hamiltonian path of weight less than or equal to VNP Completeness 38 Polynomial reduction Can we reduce the Hamiltonian path problem to the travelling salesman problem 2 – The reduction runs in O(V ) time – The Boolean answer immediately transfers backNP Completeness 39 NP Completeness Observations – All these NP problems we just saw are polynomially reducible to each other • Find a deterministic polynomialtime solution to one, you find it to all – Cook first showed this in his 1971 paper on the Boolean satisfiability problem We refer this class of most difficult class of NP problems as being NP Complete – All NP problems that are NP Hard are NP CompleteNP Completeness 40 NP Completeness Travelling salesman decision problem 01 programming problem Hamiltonian path problem Independent set problem Dominating set problem Graph coloring decision problem Clique problem Subset sum problem Vertex cover problem Subgraph isomorphism problem Boolean satisfiability problem Knapsack decision problemNP Completeness 41 NP Completeness One last question: – Are there problems that are NP but neither P nor NP Complete Ladner’s theorem says: If P = NP, then ―no‖ If P ≠ NP, then ―yes‖NP Completeness 42 NP Completeness From the description of the traveling salesman problem, there are n1  2 different Hamiltonian paths – Trying all these paths would be Q(n) – How much work is it to solve the optimization versionNP Completeness 43 NP Completeness How could we define a recursive function to solve this – Number the vertices 0, …, n – 1 – We will start at vertex 0 – Let V = 1, 2, …, n – 1 0 – Suppose we define tsp( S, k ) to be the shortest cycle visiting all the vertices in S once starting at 0 and ending at k tsp V ,0 min tsp V \ k ,k w – Now    0 0 k,0 1 kn tsp S,k min tsp S \ j , j w – In general,   jk , jS where S⊂ 1, 2, …, n – 1 – Define tsp(, k) = w 0, k – Use dynamic programming…NP Completeness 44 NP Completeness How many different arguments can be passed to tsp(S, k) n – There are at most 2 possible subsets of V – There are n – S possible second arguments n – Thus, the number of possible arguments is O(n 2 ) n – The actual number asymptotically approaches 0.25 n 2 How many calculations are there – Each calculation is S n, so an estimate to the number of calculations 2 n is O(n 2 ) 2 n – The actual number asymptotically approaches 0.125 n 2 n 2 n Thus, we require Q(n 2 ) memory with Q(n 2 ) time – As any NP Complete problem is polynomially reducible to the traveling 2 n salesman problem, the run time is O(n 2 )NP Completeness 45 NP Completeness Question: – Can we simplify this algorithm for the decision problem – Recall, we are simply asking if there is a path no greater than K – Is there any way to prune the number of possible paths taken Recall that backtracking reduced the solving of Sudoku to a few thousand iterationsNP Completeness 46 Graph isomorphisms Recall the subgraph isomorphism problem – Given two graphs, is one graph isomorphic to a subgraph of the other A possibly easier question is: – Are two graphs isomorphic O nn ln   2 – So far, the best algorithm is NP Completeness 47 Prime factors On the other hand, the problem Does n have a prime factor p less than or equal to m was shown in 2002 to be in P – Yes, people are still looking into thisNP Completeness 48 Other complexity classes The upshot is: – If you need to solve an NP Complete problem for your solution, you will require an exponential amount of time… Two other complexity classes are: – Problems that can be solved with O(ln(n)) memory: L • What can be computed with limited memory c k – Problems that can be solved in O(ln (n)) time if you have O(n ) processors: NC • What can be computed efficiently in a distributed system • This includes: – Integer multiplication and division – Matrix multiplication – Finding the determinant, inverse and rank of a matrixNP Completeness 49 Summary In this topic, we covered: – Deterministic polynomialtime algorithms P – Nondeterministic polynomialtime algorithms • Those that can be verified in deterministically in polynomial time are NP – NP Hard problems – The class of NP Complete problems – Question: is P = NPNP Completeness 50 References Wikipedia, http://en.wikipedia.org/wiki/NPcomplete Personal conversations with Therese Biedl Folkmar Bornemann, PRIMES Is in P: A Breakthrough for “Everyman” http://www.ams.org/notices/200305/feabornemann.pdf These slides are provided for the ECE 250 Algorithms and Data Structures course. The material in it reflects Douglas W. Harder’s best judgment in light of the information available to him at the time of preparation. Any reliance on these course slides by any party for any other purpose are the responsibility of such parties. Douglas W. Harder accepts no responsibility for damages, if any, suffered by any party as a result of decisions made or actions based on these course slides for any other purpose than that for which it was intended.