NP completeness ppt

NP complete problems examples ppt and np hard and np completeness ppt
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
Comment
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 © 2006-2013 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 pre-determined and linearly ordered The Turing machine we described is deterministic: – For any state-letter 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 polynomial-time algorithms A deterministic polynomial-time 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 polynomial-time 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 Held-Karp 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 Non-deterministic algorithms A Turing machine is non-deterministic if the transition table can contain more than one entry per state-letter pair – When more than one transition is possible, a non-deterministic 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 Non-deterministic algorithms A non-deterministic algorithm can be implemented on a deterministic machine in one of three manners: – Assuming execution along any branch ultimately stops, perform a depth-first 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 Non-deterministic polynomial-time algorithms A non-deterministic polynomial-time algorithm is a non-deterministic algorithm that can solve a problem on any input in polynomial timeNP Completeness 8 Non-deterministic polynomial-time algorithms The travelling salesman problem can solved non-deterministically: – 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 brute-force searchNP Completeness 9 Non-deterministic polynomial-time 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 Boolean-valued decision problemNP Completeness 10 Non-deterministic polynomial-time algorithms Currently, we don’t know any deterministic polynomial-time 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 Non-deterministic polynomial-time 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 Non-deterministic polynomial-time 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 weight?NP Completeness 13 Non-deterministic polynomial-time 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 Non-deterministic polynomial-time algorithms Note that finding the minimum-weight 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 Non-deterministic polynomial-time 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 non-deterministic 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 non-deterministic 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? Polynomial-time algorithms? Polynomial-time algorithms Exponential-time algorithms Is there a Hamiltonian cycle of length no greater than K?NP 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 polynomial-time solutions – We have already seen the travelling salesman problem – Boolean satisfiability problem – The knapsack problem – Subset sum problem – Sub-graph isomorphism problem – Hamiltonian path problem – Graph coloring problem – Clique problem – Independent set problem – Vertex cover problem – Dominating set problem – Integer programming problem