NP and NP-CompletenessOutlineSlide 3Decision and Optimization ProblemsComplexity Class PComplexity Class NPRelation of P and NPPolynomial-Time ReducibilityNP-Hard and NP-CompleteSlide 10TSPCircuit-SATKnapsackPTASBacktrackingSlide 16Branch-and-BoundSlide 18SummaryReferencesNP and NP-NP and NP-CompletenessCompletenessBryan PearsaulBryan PearsaulOutlineOutlineDecision and Optimization ProblemsDecision and Optimization ProblemsP and NPP and NPPolynomial-Time ReducibilityPolynomial-Time ReducibilityNP-Hardness and NP-CompletenessNP-Hardness and NP-CompletenessExamples: TSP, Circuit-SAT, KnapsackExamples: TSP, Circuit-SAT, KnapsackPolynomial-Time Approximation Polynomial-Time Approximation SchemesSchemesOutlineOutlineBacktrackingBacktrackingBranch-and-BoundBranch-and-BoundSummarySummaryReferencesReferencesDecision and Optimization Decision and Optimization ProblemsProblemsDecision Problem: computational Decision Problem: computational problem with intended output of problem with intended output of “yes” or “no”, 1 or 0“yes” or “no”, 1 or 0Optimization Problem: computational Optimization Problem: computational problem where we try to maximize or problem where we try to maximize or minimize some valueminimize some valueIntroduce parameter k and ask if the Introduce parameter k and ask if the optimal value for the problem is a optimal value for the problem is a most or at least k. Turn optimization most or at least k. Turn optimization into decisioninto decisionComplexity Class PComplexity Class PDeterministic in natureDeterministic in natureSolved by conventional computers in Solved by conventional computers in polynomial timepolynomial time•O(1)O(1)ConstantConstant•O(log n)O(log n)Sub-linearSub-linear•O(n)O(n)LinearLinear•O(n log n)O(n log n)Nearly LinearNearly Linear•O(nO(n22))QuadraticQuadraticPolynomial upper and lower boundsPolynomial upper and lower boundsComplexity Class NPComplexity Class NPNon-deterministic part as wellNon-deterministic part as wellchoose(b): choose a bit in a non-choose(b): choose a bit in a non-deterministic way and assign to bdeterministic way and assign to bIf someone tells us the solution to a If someone tells us the solution to a problem, we can verify it in polynomial problem, we can verify it in polynomial timetimeTwo Properties: non-deterministic method Two Properties: non-deterministic method to generate possible solutions, to generate possible solutions, deterministic method to verify in deterministic method to verify in polynomial time that the solution is polynomial time that the solution is correct.correct.Relation of P and NPRelation of P and NPP is a subset of NPP is a subset of NP““P = NP”?P = NP”?Language L is in NP, complement of L Language L is in NP, complement of L is in co-NPis in co-NPco-NP ≠ NPco-NP ≠ NPP ≠ co-NPP ≠ co-NPPolynomial-Time ReducibilityPolynomial-Time ReducibilityLanguage L is polynomial-time Language L is polynomial-time reducible to language M if there is a reducible to language M if there is a function computable in polynomial function computable in polynomial time that takes an input x of L and time that takes an input x of L and transforms it to an input f(x) of M, transforms it to an input f(x) of M, such that x is a member of L if and such that x is a member of L if and only if f(x) is a member of M.only if f(x) is a member of M.Shorthand, LShorthand, LpolypolyM means L is M means L is polynomial-time reducible to Mpolynomial-time reducible to MNP-Hard and NP-CompleteNP-Hard and NP-CompleteLanguage M is NP-hard if every other Language M is NP-hard if every other language L in NP is polynomial-time language L in NP is polynomial-time reducible to Mreducible to MFor every L that is a member of NP, For every L that is a member of NP, LLpolypolyMMIf language M is NP-hard and also in If language M is NP-hard and also in the class of NP itself, then M is NP-the class of NP itself, then M is NP-completecompleteNP-Hard and NP-CompleteNP-Hard and NP-CompleteRestriction: A known NP-complete problem Restriction: A known NP-complete problem M is actually just a special case of LM is actually just a special case of LLocal replacement: reduce a known NP-Local replacement: reduce a known NP-complete problem M to L by dividing complete problem M to L by dividing instances of M and L into “basic units” instances of M and L into “basic units” then showing each unit of M can be then showing each unit of M can be converted to a unit of Lconverted to a unit of LComponent design: reduce a known NP-Component design: reduce a known NP-complete problem M to L by building complete problem M to L by building components for an instance of L that components for an instance of L that enforce important structural functions for enforce important structural functions for instances of M.instances of M.TSPTSPFor each two cities, an integer cost is given to For each two cities, an integer cost is given to travel from one of the two cities to the other. The travel from one of the two cities to the other. The salesperson wants to make a minimum cost salesperson wants to make a minimum cost circuit visiting each city exactly once.circuit visiting each city exactly once.3111223412212244151i = 232Circuit-SATCircuit-SATLogic GatesNOTANDOR1110001111100Take a Boolean circuit with a single output Take a Boolean circuit with a single output node and ask whether there is an node and ask whether there is an assignment of values to the circuit’s inputs assignment of values to the circuit’s inputs so that the output is “1”so that the output is “1”KnapsackKnapsackGiven Given ss and and w w can we translate a can we translate a subset of rectangles to have their subset of rectangles to have their bottom edges on L so that the total bottom edges on L so that the total area of the rectangles touching L is at area of the rectangles touching L is at least least ww??sL1234567PTASPTASPolynomial-Time Approximation Polynomial-Time Approximation SchemesSchemesMuch faster, but not guaranteed to Much faster, but not guaranteed to find the best solutionfind the best solutionCome as close to the optimum value Come as close to the optimum value as possible in a reasonable amount as possible in a reasonable amount of timeof timeTake advantage of rescalability Take advantage of rescalability
View Full Document