DOC PREVIEW
SJSU ISE 230 - NP-hardness

This preview shows page 1-2-3-21-22-23-42-43-44 out of 44 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

NP-hardnessMoving towards complexity theoryOverview of complexityWhat do we mean by a problem?Instances versus problemPowerPoint PresentationExample: Sorting a list of n items by using a greedy approachA quick analysis of greedy sortingSlide 9Slide 10Overview of next few slidesSlide 12Slide 13On Polynomial Time AlgorithmsSlide 15Can integer programming be solved in polynomial time?Hard problems in practiceSlide 18Slide 19Slide 20Slide 21The class NP-easyThe housing problemSlide 240-1 Integer Programming is NP-easySome More NP-easy ProblemsQuestion of the millennium: is there a polynomial time algorithm for all NP-easy problems?On NP-easy problemsOther problems that are NP-easyOn NP-easy optimization problemsA problem that is not NP-easy.Another Problem that is not NP-easyNP-easyThe class NP-hardNP-equivalence and other classesOn NP-hardnessSome examples of NP-hard problemsProving that a problem is hardOn Proving NP-hardness resultsA transformationClaim 1: If there is a hamiltonian cycle in the original graph then there is a hamiltonian path in the transformed graph.Claim 1: If there is a hamiltonian path in the transformed graph then there is a hamiltonian cycle in the original graph.Proofs of NP-hardness transformations have two partsSummary on complexity theory.MIT and James Orlin © 20031NP-hardnessMIT and James Orlin © 20032Moving towards complexity theoryLinear Programming is viewed as easy and Integer Programming is viewed as hard”Next, we address some theoretical ways of characterizing easy vs. hard problemsOften referred to as the theory of NP-completeness or NP-hardnessMIT and James Orlin © 20033Overview of complexityHow can we show a problem is efficiently solvable?–We can show it constructively. We provide an algorithm and show that it solves the problem efficiently.How can we show a problem is not efficiently solvable?–How do you prove a negative?–This is the aim of complexity theory, which is the topic of today’s lecture.–The approach today is non-standard in that it covers half of the usual definitions of an intro to complexityMIT and James Orlin © 20034What do we mean by a problem?Consider maximize 3x + 4y subject to 4x + 5y  23 x  0 , y  0This is an “instance” of linear programming.When we say the linear programming problem, we refer to the collection of all instances.Similar, the integer programming problem (or integer programming) refers to the collection of all instances of integer programmingThe traveling salesman problem refers to all instances of the traveling salesman problemetc.MIT and James Orlin © 20035Instances versus problemComplexity theory addresses the following problem: when is a problem hard?Note: it does not deal with the question of whether any instance is hard.MIT and James Orlin © 20036General FactAs problem instances get larger, the time to solve the problem grows.But how fast?We say that a problem is solvable in polynomial time if there is a polynomial p( ) such that the time to solve a problem of size n is at most p(n).MIT and James Orlin © 20037Example: Sorting a list of n items by using a greedy approach4 3 9 12 14 11 7 10 8 24 53 4 9 12 14 11 7 10 8 2453 4 9 12 14 11 7 10 8 24 534 573 4 9 12 14 11 10 8 245 7 83 4 9 12 14 11 10 245 7 8 9 103 4 9 12 14 11 245 7 8 9 10 11143 4 9 12 14 245 7 8 9 10 11 12 2414Greedy sorting: for i = 1 to n, choose the ith least item on the list and put it in position i.MIT and James Orlin © 20038A quick analysis of greedy sorting3 4 9 12 14 11 10 8 245 7 8Suppose that there are n items. How many have to be scanned to find the next largest item?How much time does it take to insert the next largest item in the correct place?Claim: the running time is at most 100 n2. This is a polynomial time algorithm.The best possible time for sorting is around n log n.MIT and James Orlin © 20039General FactExamples: –Finding an word in a dictionary with n entries. Time  log n, depending on assumptions. Polynomial time–Sorting n itemstime  n log nPolynomial time–Finding the shortest path from s to ttime  n2. Polynomial time–Complete enumeration of a binary integer program on n variables: time > 2n.Exponential time (not polynomial time)MIT and James Orlin © 200310Running times as n growsgrowth rates1.0E+001.0E+031.0E+061.0E+091.0E+121.0E+151.0E+181 6 11 16 21 26 31 36 41 46nrunning timelog nn log nn^22^nMIT and James Orlin © 200311Overview of next few slidesEasy problems: running time is guaranteed to grow slower than a polynomial in the size of the input.Hard problems are everything else.Next: what do we mean by the size of the input?MIT and James Orlin © 200312Polynomial Time AlgorithmsFor any instance I of a problem, let S(I) be the number of inputs.–Examples. For an integer programming instance, S  m x n–For a capital budgeting instance, S  n.–What would the size of a TSP on n cities be?Let M(I) be the largest integer in the data.–We assume that integers are expressed in binary.–Consider the problem of determining whether a number M is prime. •It’s size grows as log M. (The size is not just 1).Size(I) is the number of digits to represent I. S(I) + log M(I)  Size(I)  S(I)  log M(I)MIT and James Orlin © 200313Polynomial time algorithmsThe algorithm A for problem X runs in polynomial time if the number of steps taken by A on any instance I is bounded by a polynomial in size(I). Equivalently, there is some polynomial p, so that for every instance I, the number of steps taken by A is less than p(S(I) + log M(I))).e.g., Suppose the number of steps is less than 1000  size(I)7  1000  [S(I)  log M(I)]7  1000  [S(I) + log M(I)]14Interesting fact: everyone in complexity talks about the size of the problem, but almost no one cares about measuring it precisely.MIT and James Orlin © 200314On Polynomial Time AlgorithmsWe consider a problem X to be “easy” or efficiently solvable, if there is a polynomial time algorithm A for solving X.We let P denote the class of problems solvable in polynomial time.Some more problems that are in the class P include:–Linear Programming–The assignment problem and transportation problem and minimum cost flow problem–Finding a topological order–Finding a critical path–Finding an Eulerian cycleMIT and James Orlin © 200315Which are polynomial time


View Full Document

SJSU ISE 230 - NP-hardness

Download NP-hardness
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view NP-hardness and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view NP-hardness 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?