Алгоритмы для NP-трудных задач, осень 2016: Задачи поиска

  • Published on
    15-Apr-2017

  • View
    173

  • Download
    4

Embed Size (px)

Transcript

<ul><li><p>NP-complete Problems:Search Problems</p><p>Alexander S. KulikovSteklov Institute of Mathematics at St. Petersburg</p><p>Russian Academy of Sciences</p><p>Advanced Algorithms and ComplexityData Structures and Algorithms</p><p>https://www.coursera.org/learn/advanced-algorithms-and-complexityhttps://goo.gl/KAfKJT</p></li><li><p>Outline1 Brute Force Search</p><p>2 Search Problems</p><p>3 Easy and Hard ProblemsTraveling Salesman ProblemHamiltonian Cycle ProblemLongest Path ProblemInteger Linear Programming ProblemIndependent Set Problem</p><p>4 P and NP</p></li><li><p>Polynomial vs Exponential</p><p>running time: n n2 n3 2n</p><p>less than 109: 109 104.5 103 29</p></li><li><p>Improving Brute Force Search</p><p>Usually, an efficient (polynomial) algorithmsearches for a solution among an exponentialnumber of candidates:</p><p>there are n! permutations of n objects</p><p>there are 2n ways to partition n objectsinto two setsthere are nn2 spanning trees in acomplete graph on n vertices</p></li><li><p>Improving Brute Force Search</p><p>Usually, an efficient (polynomial) algorithmsearches for a solution among an exponentialnumber of candidates:</p><p>there are n! permutations of n objectsthere are 2n ways to partition n objectsinto two sets</p><p>there are nn2 spanning trees in acomplete graph on n vertices</p></li><li><p>Improving Brute Force Search</p><p>Usually, an efficient (polynomial) algorithmsearches for a solution among an exponentialnumber of candidates:</p><p>there are n! permutations of n objectsthere are 2n ways to partition n objectsinto two setsthere are nn2 spanning trees in acomplete graph on n vertices</p></li><li><p>This module</p><p>For thousands of practically importantproblems we dont have an efficientalgorithm yet</p><p>An efficient algorithm for one suchproblem automatically gives efficientalgorithms for all these problems!$1M prize for constructing such analgorithm or proving that this isimpossible!</p></li><li><p>This module</p><p>For thousands of practically importantproblems we dont have an efficientalgorithm yetAn efficient algorithm for one suchproblem automatically gives efficientalgorithms for all these problems!</p><p>$1M prize for constructing such analgorithm or proving that this isimpossible!</p></li><li><p>This module</p><p>For thousands of practically importantproblems we dont have an efficientalgorithm yetAn efficient algorithm for one suchproblem automatically gives efficientalgorithms for all these problems!$1M prize for constructing such analgorithm or proving that this isimpossible!</p></li><li><p>Outline1 Brute Force Search</p><p>2 Search Problems</p><p>3 Easy and Hard ProblemsTraveling Salesman ProblemHamiltonian Cycle ProblemLongest Path ProblemInteger Linear Programming ProblemIndependent Set Problem</p><p>4 P and NP</p></li><li><p>Boolean Formulas</p><p>Formula in conjunctive normal form</p><p>(x y z)(x y)(y z)(z x)(x y z)x , y , z are Boolean variables (values:true/false or 1/0)literals are variables (x , y , z) and theirnegations (x , y , z)clauses are disjunctions (logical or) ofliterals</p></li><li><p>Satisfiability (SAT)</p><p>Input: Formula F in conjunctive normalform (CNF).</p><p>Output: An assignment of Boolean values tothe variables of F satisfying allclauses, if exists.</p></li><li><p>Examples</p><p>The formula (x y)(x y)(x y) issatisfiable: set x = 1, y = 0.The formula (x y z)(x y)(y z) issatisfiable: set x = 1, y = 1, z = 1 orx = 1, y = 0, z = 0.The formula(xy z)(xy)(y z)(zx)(xy z)is unsatisfiable.</p></li><li><p>Satisfiability</p><p>Classical hard problemMany applications: e.g.,hardware/software verification, planning,schedulingMany hard problems are stated in termsof SAT naturallySAT solvers (will see later), SATcompetition</p></li><li><p>SAT is a typical search problemSearch problem: given an instance I ,find a solution S or report that noneexistsMain property: one must be able tocheck quickly whether S is indeed asolution for IBy saying quickly, we mean in timepolynomial in the length of I . Inparticular, the length of S should bepolynomial in the length of I</p></li><li><p>DefinitionA search problem is defined by analgorithm that takes an instance I anda candidate solution S , and runs in timepolynomial in the length of I . We say that Sis a solution to I iff (S , I ) = true.</p></li><li><p>Example</p><p>For SAT, I is a Boolean formula, S is anassignment of Boolean constants to itsvariables. The corresponding algorithm checks whether S satisfies all clauses of I .</p></li><li><p>Next part</p><p>A few practical search problems for whichpolynomial algorithms remain unknown</p></li><li><p>Outline1 Brute Force Search</p><p>2 Search Problems</p><p>3 Easy and Hard ProblemsTraveling Salesman ProblemHamiltonian Cycle ProblemLongest Path ProblemInteger Linear Programming ProblemIndependent Set Problem</p><p>4 P and NP</p></li><li><p>Outline1 Brute Force Search</p><p>2 Search Problems</p><p>3 Easy and Hard ProblemsTraveling Salesman ProblemHamiltonian Cycle ProblemLongest Path ProblemInteger Linear Programming ProblemIndependent Set Problem</p><p>4 P and NP</p></li><li><p>Traveling salesman problem (TSP)</p><p>Input: Pairwise distances between n citiesand a budget b.</p><p>Output: A cycle that visits each vertexexactly once and has total length atmost b.</p></li><li><p>Delivery Company</p><p>https://simple.wikipedia.org/wiki/Travelling_salesman_problem</p><p>https://simple.wikipedia.org/wiki/Travelling_salesman_problem</p></li><li><p>Drilling Holes in a Circuit Board</p><p>https://developers.google.com/optimization/routing/tsp</p><p>https://developers.google.com/optimization/routing/tsp</p></li><li><p>Example</p><p>1</p><p>2</p><p>5</p><p>3</p><p>4</p><p>5</p><p>2</p><p>4</p><p>2</p><p>2</p><p>1</p><p>13</p><p>33</p></li><li><p>Example</p><p>1</p><p>2</p><p>5</p><p>3</p><p>4</p><p>5</p><p>2</p><p>4</p><p>2</p><p>2</p><p>1</p><p>13</p><p>33</p><p>length: 15</p></li><li><p>Example</p><p>1</p><p>2</p><p>5</p><p>3</p><p>4</p><p>5</p><p>2</p><p>4</p><p>2</p><p>2</p><p>1</p><p>13</p><p>33</p><p>length: 13</p></li><li><p>Example</p><p>1</p><p>2</p><p>5</p><p>3</p><p>4</p><p>5</p><p>2</p><p>4</p><p>2</p><p>2</p><p>1</p><p>13</p><p>33</p><p>length: 9</p></li><li><p>Search Problem</p><p>TSP is a search problem: given asequence of vertices, it is easy to checkwhether it is a cycle visiting all thevertices of total length at most bTSP is usually stated as an optimizationproblem; we stated its decision versionto guarantee that a candidate solutioncan be efficiently checked for correctness</p></li><li><p>Algorithms</p><p>Check all permutations: about O(n!),extremely slowDynamic programming: O(n22n)No significantly better upper bound isknownThere are heuristic algorithms andapproximation algorithms</p></li><li><p>Comparing to MSTMSTDecision version:given n cities, connectthem by (n 1) roadsof minimal totallength</p><p>Can be solvedefficiently</p><p>TSPDecision version:given n cities, connectthem in a path by(n 1) roads ofminimal total length</p><p>No polynomialalgorithm known!</p></li><li><p>Comparing to MSTMSTDecision version:given n cities, connectthem by (n 1) roadsof minimal totallength</p><p>Can be solvedefficiently</p><p>TSPDecision version:given n cities, connectthem in a path by(n 1) roads ofminimal total length</p><p>No polynomialalgorithm known!</p></li><li><p>Comparing to MSTMSTDecision version:given n cities, connectthem by (n 1) roadsof minimal totallength</p><p>Can be solvedefficiently</p><p>TSPDecision version:given n cities, connectthem in a path by(n 1) roads ofminimal total length</p><p>No polynomialalgorithm known!</p></li><li><p>Comparing to MSTMSTDecision version:given n cities, connectthem by (n 1) roadsof minimal totallength</p><p>Can be solvedefficiently</p><p>TSPDecision version:given n cities, connectthem in a path by(n 1) roads ofminimal total length</p><p>No polynomialalgorithm known!</p></li><li><p>Outline1 Brute Force Search</p><p>2 Search Problems</p><p>3 Easy and Hard ProblemsTraveling Salesman ProblemHamiltonian Cycle ProblemLongest Path ProblemInteger Linear Programming ProblemIndependent Set Problem</p><p>4 P and NP</p></li><li><p>Hamiltonian cycle</p><p>Input: A graph.Output: A cycle that visits each vertex of</p><p>the graph exactly once.</p></li><li><p>Example</p></li><li><p>Example</p></li><li><p>Eulerian cycle</p><p>Input: A graph.Output: A cycle that visits each edge of the</p><p>graph exactly once.</p><p>TheoremA graph has an Eulerian cycle if and only if itis connected and the degree of each vertex iseven.</p></li><li><p>Eulerian cycle</p><p>Input: A graph.Output: A cycle that visits each edge of the</p><p>graph exactly once.</p><p>TheoremA graph has an Eulerian cycle if and only if itis connected and the degree of each vertex iseven.</p></li><li><p>Non-Eulerian graph</p><p>Eulerian graph</p></li><li><p>Non-Eulerian graph Eulerian graph</p></li><li><p>Eulerian cycle</p><p>Find a cycle visitingeach edge exactlyonce</p><p>Can be solvedefficiently</p><p>Hamiltonian cycle</p><p>Find a cycle visitingeach vertex exactlyonce</p><p>No polynomialalgorithm known!</p></li><li><p>Eulerian cycle</p><p>Find a cycle visitingeach edge exactlyonce</p><p>Can be solvedefficiently</p><p>Hamiltonian cycle</p><p>Find a cycle visitingeach vertex exactlyonce</p><p>No polynomialalgorithm known!</p></li><li><p>Eulerian cycle</p><p>Find a cycle visitingeach edge exactlyonce</p><p>Can be solvedefficiently</p><p>Hamiltonian cycle</p><p>Find a cycle visitingeach vertex exactlyonce</p><p>No polynomialalgorithm known!</p></li><li><p>Eulerian cycle</p><p>Find a cycle visitingeach edge exactlyonce</p><p>Can be solvedefficiently</p><p>Hamiltonian cycle</p><p>Find a cycle visitingeach vertex exactlyonce</p><p>No polynomialalgorithm known!</p></li><li><p>Outline1 Brute Force Search</p><p>2 Search Problems</p><p>3 Easy and Hard ProblemsTraveling Salesman ProblemHamiltonian Cycle ProblemLongest Path ProblemInteger Linear Programming ProblemIndependent Set Problem</p><p>4 P and NP</p></li><li><p>Longest path</p><p>Input: A weighted graph, two vertices s, t,and a budget b.</p><p>Output: A simple path (containing norepeated vertices) of total length atleast b.</p></li><li><p>Example</p></li><li><p>Example</p></li><li><p>Example</p></li><li><p>Example</p></li><li><p>Shortest path</p><p>Find a simple pathfrom s to t of totallength at most b</p><p>Can be solvedefficiently</p><p>Longest path</p><p>Find a simple pathfrom s to t of totallength at least b</p><p>No polynomialalgorithm known!</p></li><li><p>Shortest path</p><p>Find a simple pathfrom s to t of totallength at most b</p><p>Can be solvedefficiently</p><p>Longest path</p><p>Find a simple pathfrom s to t of totallength at least b</p><p>No polynomialalgorithm known!</p></li><li><p>Shortest path</p><p>Find a simple pathfrom s to t of totallength at most b</p><p>Can be solvedefficiently</p><p>Longest path</p><p>Find a simple pathfrom s to t of totallength at least b</p><p>No polynomialalgorithm known!</p></li><li><p>Shortest path</p><p>Find a simple pathfrom s to t of totallength at most b</p><p>Can be solvedefficiently</p><p>Longest path</p><p>Find a simple pathfrom s to t of totallength at least b</p><p>No polynomialalgorithm known!</p></li><li><p>Outline1 Brute Force Search</p><p>2 Search Problems</p><p>3 Easy and Hard ProblemsTraveling Salesman ProblemHamiltonian Cycle ProblemLongest Path ProblemInteger Linear Programming ProblemIndependent Set Problem</p><p>4 P and NP</p></li><li><p>Integer linear programming</p><p>Input: A set of linear inequalities Ax b.Output: Integer solution.</p></li><li><p>Example</p><p>x1 0.5x1 + 8x2 0x1 8x2 8</p></li><li><p>Example</p><p>x1 0.5x1 + 8x2 0x1 8x2 8</p><p>x1</p><p>x2</p></li><li><p>Example</p><p>x1 0.5x1 + 8x2 0x1 8x2 8</p><p>x1</p><p>x2</p></li><li><p>Example</p><p>x1 0.5x1 + 8x2 0x1 8x2 8</p><p>x1</p><p>x2</p></li><li><p>Example</p><p>x1 0.5x1 + 8x2 0x1 8x2 8</p><p>x1</p><p>x2</p></li><li><p>LP(decision version)</p><p>Find a realsolution of a system oflinear inequalities</p><p>Can be solvedefficiently</p><p>ILP</p><p>Find an integersolution of a system oflinear inequalities</p><p>No polynomialalgorithm known!</p></li><li><p>LP(decision version)</p><p>Find a realsolution of a system oflinear inequalities</p><p>Can be solvedefficiently</p><p>ILP</p><p>Find an integersolution of a system oflinear inequalities</p><p>No polynomialalgorithm known!</p></li><li><p>LP(decision version)</p><p>Find a realsolution of a system oflinear inequalities</p><p>Can be solvedefficiently</p><p>ILP</p><p>Find an integersolution of a system oflinear inequalities</p><p>No polynomialalgorithm known!</p></li><li><p>LP(decision version)</p><p>Find a realsolution of a system oflinear inequalities</p><p>Can be solvedefficiently</p><p>ILP</p><p>Find an integersolution of a system oflinear inequalities</p><p>No polynomialalgorithm known!</p></li><li><p>Outline1 Brute Force Search</p><p>2 Search Problems</p><p>3 Easy and Hard ProblemsTraveling Salesman ProblemHamiltonian Cycle ProblemLongest Path ProblemInteger Linear Programming ProblemIndependent Set Problem</p><p>4 P and NP</p></li><li><p>Independent set</p><p>Input: A graph and a budget b.Output: A subset of vertices of size at least</p><p>b such that no two of them areadjacent.</p></li><li><p>Example</p></li><li><p>Example</p></li><li><p>Independent Sets in a Tree</p><p>A maximal independent set in a tree can befound by a simple greedy algorithm: it is safeto take into a solution all the leaves.</p></li><li><p>Independent set ina tree</p><p>Find an independentset of size at least b ina given tree</p><p>Can be solvedefficiently</p><p>Independent set ina graph</p><p>Find an independentset of size at least b ina given graph</p><p>No polynomialalgorithm known!</p></li><li><p>Independent set ina tree</p><p>Find an independentset of size at least b ina given tree</p><p>Can be solvedefficiently</p><p>Independent set ina graph</p><p>Find an independentset of size at least b ina given graph</p><p>No polynomialalgorithm known!</p></li><li><p>Independent set ina tree</p><p>Find an independentset of size at least b ina given tree</p><p>Can be solvedefficiently</p><p>Independent set ina graph</p><p>Find an independentset of size at least b ina given graph</p><p>No polynomialalgorithm known!</p></li><li><p>Independent set ina tree</p><p>Find an independentset of size at least b ina given tree</p><p>Can be solvedefficiently</p><p>Independent set ina graph</p><p>Find an independentset of size at least b ina given graph</p><p>No polynomialalgorithm known!</p></li><li><p>Next part</p><p>It turns out that all these hard problems arein a sense a single hard problem:a polynomial time algorithm for any of theseproblems can be used to solve all of them inpolynomial time!</p></li><li><p>Outline1 Brute Force Search</p><p>2 Search Problems</p><p>3 Easy and Hard ProblemsTraveling Salesman ProblemHamiltonian Cycle ProblemLongest Path ProblemInteger Linear Programming ProblemIndependent Set Problem</p><p>4 P and NP</p></li><li><p>Class NPDefinitionA search problem is defined by analgorithm that takes an instance I anda candidate solution S , and runs in timepolynomial in the length of I . We say that Sis a solution to I iff (S , I ) = true.</p><p>DefinitionNP is the class of all search problems.</p></li><li><p>Class NPDefinitionA search problem is defined by analgorithm that takes an instance I anda candidate solution S , and runs in timepolynomial in the length of I . We say that Sis a solution to I iff (S , I ) = true.</p><p>DefinitionNP is the class of all search problems.</p></li><li><p>NP stands for non-deterministicpolynomial time: one can guess asolution, and then verify its correctnessin polynomial timeIn other words, the class NP containsall problems whose solutions can beefficiently verified</p></li><li><p>Class P</p><p>DefinitionP is the class of all search problems that canbe solved in polynomial time.</p></li><li><p>Class PProblems whosesolution can befound efficiently</p><p>MSTShortest pathLPIS on trees</p><p>Class NPProblems whosesolution can beverified efficiently</p><p>TSPLongest pathILPIS on graphs</p></li><li><p>Class PProblems whosesolution can befound efficiently</p><p>MSTShortest pathLPIS on trees</p><p>Class NPProblems whosesolution can beverified efficiently</p><p>TSPLongest pathILPIS on graphs</p></li><li><p>Class PProblems whosesolution can befound efficiently</p><p>MSTShortest pathLPIS on trees</p><p>Class NPProblems whosesolution can beverified efficiently</p><p>TSPLongest pathILPIS on graphs</p></li><li><p>Class PProblems whosesolution can befound efficiently</p><p>MSTShortest pathLPIS on trees</p><p>Class NPProblems whosesolution can beverified efficiently</p><p>TSPLongest pathILPIS on graphs</p></li><li><p>The main open problem in ComputerScience</p><p>Is P equal to NP?</p><p>Millenium Prize ProblemClay Mathematics Institute: $1M prize forsolving the problem</p></li><li><p>The main open problem in ComputerScience</p><p>Is P equal to NP?</p><p>Millenium Prize ProblemClay Mathematics Institute: $1M prize forsolving the problem</p></li><li><p>If P=NP, then all search problems canbe solved in polynomial time.</p><p>If P=NP, then there exist searchproblems that cannot be solved inpolynomial time.</p></li><li><p>If P=NP, then all search problems canbe solved in polynomial time.If P=NP, then there exist searchproblems that cannot be solved inpolynomial time.</p></li><li><p>Next part</p><p>Well show that the satisfiability problem, thetraveling salesman problem, the independentset problem, the integer linear programmingare the hardest problems in NP.</p><p>Brute Force SearchSearch ProblemsEasy and Hard ProblemsTraveling Salesman ProblemHamiltonian Cycle ProblemLongest Path ProblemInteger Linear Programming ProblemIndependent Set Problem</p><p>P and NP</p></li></ul>

Recommended

View more >