PLS (complexity)

Last updated

In computational complexity theory, Polynomial Local Search (PLS) is a complexity class that models the difficulty of finding a locally optimal solution to an optimization problem. The main characteristics pls take it

Contents

of problems that lie in PLS are that the cost of a solution can be calculated in polynomial time and the neighborhood of a solution can be searched in polynomial time. Therefore it is possible to verify whether or not a solution is a local optimum in polynomial time.

Furthermore, depending on the problem and the algorithm that is used for solving the problem, it might be faster to find a local optimum instead of a global optimum.

Description

When searching for a local optimum, there are two interesting issues to deal with: First how to find a local optimum, and second how long it takes to find a local optimum. For many local search algorithms, it is not known, whether they can find a local optimum in polynomial time or not. [1] So to answer the question of how long it takes to find a local optimum, Johnson, Papadimitriou and Yannakakis [2] introduced the complexity class PLS in their paper "How easy is local search?". It contains local search problems for which the local optimality can be verified in polynomial time.

A local search problem is in PLS, if the following properties are satisfied:

With these properties, it is possible to find for each solution the best neighboring solution or if there is no such better neighboring solution, state that is a local optimum.

Example

Consider the following instance of the Max-2Sat Problem: . The aim is to find an assignment, that maximizes the sum of the satisfied clauses.

A solution for that instance is a bit string that assigns every the value 0 or 1. In this case, a solution consists of 3 bits, for example , which stands for the assignment of to with the value 0. The set of solutions is the set of all possible assignments of , and .

The cost of each solution is the number of satisfied clauses, so because the second and third clause are satisfied.

The Flip-neighbor of a solution is reached by flipping one bit of the bit string , so the neighbors of are with the following costs:

There are no neighbors with better costs than , if we are looking for a solution with maximum cost. Even though is not a global optimum (which for example would be a solution that satisfies all clauses and has ), is a local optimum, because none of its neighbors has better costs.

Intuitively it can be argued that this problem lies in PLS, because:

If we are simply counting the number of satisfied clauses, the problem can be solved in polynomial time since the number of possible costs is polynomial. However, if we assign each clause a positive integer weight (and seek to locally maximize the sum of weights of satisfied clauses), the problem becomes PLS-complete (below).

Formal Definition

A local search problem has a set of instances which are encoded using strings over a finite alphabet . For each instance there exists a finite solution set . Let be the relation that models . The relation is in PLS [2] [3] [4] if:

An instance has the structure of an implicit graph (also called Transition graph [6] ), the vertices being the solutions with two solutions connected by a directed arc iff .

A local optimum is a solution , that has no neighbor with better costs. In the implicit graph, a local optimum is a sink. A neighborhood where every local optimum is a global optimum, which is a solution with the best possible cost, is called an exact neighborhood. [6] [1]

Alternative Definition

The class PLS is the class containing all problems that can be reduced in polynomial time to the problem Sink-of-DAG [7] (also called Local-Opt [8] ): Given two integers and and two Boolean circuits such that and , find a vertex such that and either or .

Example neighborhood structures

Example neighborhood structures for problems with boolean variables (or bit strings) as solution:

Example neighborhood structures for problems on graphs:

The standard Algorithm

Consider the following computational problem: Given some instance of a PLS problem , find a locally optimal solution such that for all .

Every local search problem can be solved using the following iterative improvement algorithm: [2]

  1. Use to find an initial solution
  2. Use algorithm to find a better solution . If such a solution exists, replace by and repeat step 2, else return

Unfortunately, it generally takes an exponential number of improvement steps to find a local optimum even if the problem can be solved exactly in polynomial time. [2] It is not necessary always to use the standard algorithm, there may be a different, faster algorithm for a certain problem. For example a local search algorithm used for Linear programming is the Simplex algorithm.

The run time of the standard algorithm is pseudo-polynomial in the number of different costs of a solution. [12]

The space the standard algorithm needs is only polynomial. It only needs to save the current solution , which is polynomial bounded by definition. [1]

Reductions

A Reduction of one problem to another may be used to show that the second problem is at least as difficult as the first. In particular, a PLS-reduction is used to prove that a local search problem that lies in PLS is also PLS-complete, by reducing a PLS-complete Problem to the one that shall be proven to be PLS-complete.

PLS-reduction

A local search problem is PLS-reducible [2] to a local search problem if there are two polynomial time functions and such that:

It is sufficient to only map the local optima of to the local optima of , and to map all other solutions for example to the standard solution returned by . [6]

PLS-reductions are transitive. [2]

Tight PLS-reduction

Definition Transition graph

The transition graph [6] of an instance of a problem is a directed graph. The nodes represent all elements of the finite set of solutions and the edges point from one solution to the neighbor with strictly better cost. Therefore it is an acyclic graph. A sink, which is a node with no outgoing edges, is a local optimum. The height of a vertex is the length of the shortest path from to the nearest sink. The height of the transition graph is the largest of the heights of all vertices, so it is the height of the largest shortest possible path from a node to its nearest sink.

Definition Tight PLS-reduction

A PLS-reduction from a local search problem to a local search problem is a tight PLS-reduction [10] if for any instance of , a subset of solutions of instance of can be chosen, so that the following properties are satisfied:

  • contains, among other solutions, all local optima of
  • For every solution of , a solution of can be constructed in polynomial time, so that
  • If the transition graph of contains a direct path from to , and , but all internal path vertices are outside , then for the corresponding solutions and holds either or contains an edge from to

Relationship to other complexity classes

PLS lies between the functional versions of P and NP: FP ⊆ PLS ⊆ FNP. [2]

PLS also is a subclass of TFNP, [13] that describes computational problems in which a solution is guaranteed to exist and can be recognized in polynomial time. For a problem in PLS, a solution is guaranteed to exist because the minimum-cost vertex of the entire graph is a valid solution, and the validity of a solution can be checked by computing its neighbors and comparing the costs of each one to another.

It is also proven that if a PLS problem is NP-hard, then NP = co-NP. [2]

PLS-completeness

Definition

A local search problem is PLS-complete, [2] if

The optimization version of the circuit problem under the Flip neighborhood structure has been shown to be a first PLS-complete problem. [2]

List of PLS-complete Problems

This is an incomplete list of some known problems that are PLS-complete. The problems here are the weighted versions; for example, Max-2SAT/Flip is weighted even though Max-2SAT ordinarily refers to the unweighted version.

Overview of PLS-complete problems and how they are reduced to each other. Syntax: Optimization-Problem/Neighborhood structure. Dotted arrow: PLS-reduction from a problem
L
{\displaystyle L}
to a problem
Q
:
L
-
Q
{\displaystyle Q:L\leftarrow Q}
. Black arrow: Tight PLS-reduction. PLS-complete Problems Overview.svg
Overview of PLS-complete problems and how they are reduced to each other. Syntax: Optimization-Problem/Neighborhood structure. Dotted arrow: PLS-reduction from a problem to a problem . Black arrow: Tight PLS-reduction.

Notation: Problem / Neighborhood structure

Relations to other complexity classes

Fearnley, Goldberg, Hollender and Savani [24] proved that a complexity class called CLS is equal to the intersection of PPAD and PLS.

Further reading

Related Research Articles

<span class="mw-page-title-main">NP (complexity)</span> Complexity class used to classify decision problems

In computational complexity theory, NP is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine, or alternatively the set of problems that can be solved in polynomial time by a nondeterministic Turing machine.

<span class="mw-page-title-main">Travelling salesman problem</span> NP-hard problem in combinatorial optimization

The travelling salesman problem, also known as the travelling salesperson problem (TSP), asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.

<span class="mw-page-title-main">Linear programming</span> Method to solve optimization problems

Linear programming (LP), also called linear optimization, is a method to achieve the best outcome in a mathematical model whose requirements and objective are represented by linear relationships. Linear programming is a special case of mathematical programming.

<span class="mw-page-title-main">Assignment problem</span> Combinatorial optimization problem

The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows:

<span class="mw-page-title-main">Combinatorial optimization</span> Subfield of mathematical optimization

Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combinatorial optimization problems are the travelling salesman problem ("TSP"), the minimum spanning tree problem ("MST"), and the knapsack problem. In many such problems, such as the ones previously mentioned, exhaustive search is not tractable, and so specialized algorithms that quickly rule out large parts of the search space or approximation algorithms must be resorted to instead.

In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems with provable guarantees on the distance of the returned solution to the optimal one. Approximation algorithms naturally arise in the field of theoretical computer science as a consequence of the widely believed P ≠ NP conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in polynomial time. The field of approximation algorithms, therefore, tries to understand how closely it is possible to approximate optimal solutions to such problems in polynomial time. In an overwhelming majority of the cases, the guarantee of such algorithms is a multiplicative one expressed as an approximation ratio or approximation factor i.e., the optimal solution is always guaranteed to be within a (predetermined) multiplicative factor of the returned solution. However, there are also many approximation algorithms that provide an additive guarantee on the quality of the returned solution. A notable example of an approximation algorithm that provides both is the classic approximation algorithm of Lenstra, Shmoys and Tardos for scheduling on unrelated parallel machines.

In computational complexity theory, the complexity class NEXPTIME is the set of decision problems that can be solved by a non-deterministic Turing machine using time .

In the mathematical field of spectral graph theory, a Ramanujan graph is a regular graph whose spectral gap is almost as large as possible. Such graphs are excellent spectral expanders. As Murty's survey paper notes, Ramanujan graphs "fuse diverse branches of pure mathematics, namely, number theory, representation theory, and algebraic geometry". These graphs are indirectly named after Srinivasa Ramanujan; their name comes from the Ramanujan–Petersson conjecture, which was used in a construction of some of these graphs.

<span class="mw-page-title-main">Approximation theory</span> Theory of getting acceptably close inexact mathematical calculations

In mathematics, approximation theory is concerned with how functions can best be approximated with simpler functions, and with quantitatively characterizing the errors introduced thereby. What is meant by best and simpler will depend on the application.

In computational complexity theory, the class APX is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant. In simple terms, problems in this class have efficient algorithms that can find an answer within some fixed multiplicative factor of the optimal answer.

In mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions over convex sets. The ellipsoid method generates a sequence of ellipsoids whose volume uniformly decreases at every step, thus enclosing a minimizer of a convex function.

In computational complexity theory, the complexity class TFNP is the class of total function problems which can be solved in nondeterministic polynomial time. That is, it is the class of function problems that are guaranteed to have an answer, and this answer can be checked in polynomial time, or equivalently it is the subset of FNP where a solution is guaranteed to exist. The abbreviation TFNP stands for "Total Function Nondeterministic Polynomial".

Interval scheduling is a class of problems in computer science, particularly in the area of algorithm design. The problems consider a set of tasks. Each task is represented by an interval describing the time in which it needs to be processed by some machine. For instance, task A might run from 2:00 to 5:00, task B might run from 4:00 to 10:00 and task C might run from 9:00 to 11:00. A subset of intervals is compatible if no two intervals overlap on the machine/resource. For example, the subset {A,C} is compatible, as is the subset {B}; but neither {A,B} nor {B,C} are compatible subsets, because the corresponding intervals within each subset overlap.

In mathematics, a graph partition is the reduction of a graph to a smaller graph by partitioning its set of nodes into mutually exclusive groups. Edges of the original graph that cross between the groups will produce edges in the partitioned graph. If the number of resulting edges is small compared to the original graph, then the partitioned graph may be better suited for analysis and problem-solving than the original. Finding a partition that simplifies graph analysis is a hard problem, but one that has applications to scientific computing, VLSI circuit design, and task scheduling in multiprocessor computers, among others. Recently, the graph partition problem has gained importance due to its application for clustering and detection of cliques in social, pathological and biological networks. For a survey on recent trends in computational methods and applications see Buluc et al. (2013). Two common examples of graph partitioning are minimum cut and maximum cut problems.

In computer science, a kernelization is a technique for designing efficient algorithms that achieve their efficiency by a preprocessing stage in which inputs to the algorithm are replaced by a smaller input, called a "kernel". The result of solving the problem on the kernel should either be the same as on the original input, or it should be easy to transform the output on the kernel to the desired output for the original problem.

<span class="mw-page-title-main">Maximum cut</span> Problem of finding a maximum cut in a graph

In a graph, a maximum cut is a cut whose size is at least the size of any other cut. That is, it is a partition of the graph's vertices into two complementary sets S and T, such that the number of edges between S and T is as large as possible. Finding such a cut is known as the max-cut problem.

<span class="mw-page-title-main">NP-completeness</span> Complexity class

In computational complexity theory, a problem is NP-complete when:

  1. It is a decision problem, meaning that for any input to the problem, the output is either "yes" or "no".
  2. When the answer is "yes", this can be demonstrated through the existence of a short solution.
  3. The correctness of each solution can be verified quickly and a brute-force search algorithm can find a solution by trying all possible solutions.
  4. The problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. If we could find solutions of some NP-complete problem quickly, we could quickly find the solutions of every other problem to which a given solution can be easily verified.

In graph theory, the metric k-center problem or vertex k-center problem is a classical combinatorial optimization problem studied in theoretical computer science that is NP-hard. Given n cities with specified distances, one wants to build k warehouses in different cities and minimize the maximum distance of a city to a warehouse. In graph theory, this means finding a set of k vertices for which the largest distance of any point to its closest vertex in the k-set is minimum. The vertices must be in a metric space, providing a complete graph that satisfies the triangle inequality. It has application in facility location and clustering.

The quadratic knapsack problem (QKP), first introduced in 19th century, is an extension of knapsack problem that allows for quadratic terms in the objective function: Given a set of items, each with a weight, a value, and an extra profit that can be earned if two items are selected, determine the number of items to include in a collection without exceeding capacity of the knapsack, so as to maximize the overall profit. Usually, quadratic knapsack problems come with a restriction on the number of copies of each kind of item: either 0, or 1. This special type of QKP forms the 0-1 quadratic knapsack problem, which was first discussed by Gallo et al. The 0-1 quadratic knapsack problem is a variation of knapsack problems, combining the features of unbounded knapsack problem, 0-1 knapsack problem and quadratic knapsack problem.

Quadratic pseudo-Boolean optimisation (QPBO) is a combinatorial optimization method for minimizing quadratic pseudo-Boolean functions in the form

References

  1. 1 2 3 4 5 6 7 8 9 10 11 12 Yannakakis, Mihalis (2003). Local search in combinatorial optimization - Computational complexity. Princeton University Press. pp. 19–55. ISBN   9780691115221.
  2. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Johnson, David S; Papadimitriou, Christos H; Yannakakis, Mihalis (1988). "How easy is local search?". Journal of Computer and System Sciences. 37 (1): 79–100. doi: 10.1016/0022-0000(88)90046-3 .
  3. 1 2 Mulzer, Wolfgang; Stein, Yannik (14 March 2018). "Computational Aspects of the Colorful Caratheodory Theorem". Discrete & Computational Geometry . 60 (3): 720–755. arXiv: 1412.3347 . Bibcode:2014arXiv1412.3347M. doi:10.1007/s00454-018-9979-y. S2CID   254024141.
  4. 1 2 Borzechowski, Michaela. "The complexity class Polynomial Local Search (PLS) and PLS-complete problems" (PDF).
  5. 1 2 3 4 Dumrauf, Dominic; Monien, Burkhard; Tiemann, Karsten (2009). "Multiprocessor Scheduling is PLS-Complete". System Sciences, 2009. HICSS'09. 42nd Hawaii International Conference on: 1–10.
  6. 1 2 3 4 5 6 7 Michiels, Wil; Aarts, Emile; Korst, Jan (2010). Theoretical aspects of local search. Springer Science & Business Media. ISBN   9783642071485.
  7. Fearnley, John; Gordon, Spencer; Mehta, Ruta; Savani, Rahul (December 2020). "Unique end of potential line". Journal of Computer and System Sciences. 114: 1–35. arXiv: 1811.03841 . doi:10.1016/j.jcss.2020.05.007.
  8. 1 2 Daskalakis, Constantinos; Papadimitriou, Christos (23 January 2011). "Continuous Local Search". Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms: 790–804. doi:10.1137/1.9781611973082.62. ISBN   978-0-89871-993-2. S2CID   2056144.
  9. 1 2 3 4 5 Klauck, Hartmut (1996). "On the hardness of global and local approximation". Proceedings of the 5th Scandinavian Workshop on Algorithm Theory: 88–99.
  10. 1 2 3 4 5 6 7 8 9 Schäffer, Alejandro A.; Yannakakis, Mihalis (February 1991). "Simple Local Search Problems that are Hard to Solve". SIAM Journal on Computing. 20 (1): 56–87. doi:10.1137/0220004.
  11. Fiduccia, C. M.; Mattheyses, R. M. (1982). "A Linear-time Heuristic for Improving Network Partitions". Proceedings of the 19th Design Automation Conference: 175–181. ISBN   9780897910200.
  12. Angel, Eric; Christopoulos, Petros; Zissimopoulos, Vassilis (2014). Paradigms of Combinatorial Optimization: Problems and New Approaches - Local Search: Complexity and Approximation (2 ed.). John Wiley & Sons, Inc., Hoboken. pp. 435–471. doi:10.1002/9781119005353.ch14. ISBN   9781119005353.
  13. Megiddo, Nimrod; Papadimitriou, Christos H (1991). "On total functions, existence theorems and computational complexity". Theoretical Computer Science. 81 (2): 317–324. CiteSeerX   10.1.1.75.4797 . doi: 10.1016/0304-3975(91)90200-L .
  14. Krentel, M. (1 August 1990). "On Finding and Verifying Locally Optimal Solutions". SIAM Journal on Computing. 19 (4): 742–749. doi:10.1137/0219052. ISSN   0097-5397.
  15. 1 2 3 Krentel, Mark W. (1989). "Structure in locally optimal solutions". 30th Annual Symposium on Foundations of Computer Science. pp. 216–221. doi:10.1109/SFCS.1989.63481. ISBN   0-8186-1982-1. S2CID   32686790.
  16. Shimozono, Shinichi (1997). "Finding optimal subgraphs by local search". Theoretical Computer Science. 172 (1): 265–271. doi: 10.1016/S0304-3975(96)00135-1 .
  17. Dumrauf, Dominic; Süß, Tim (2010). "On the Complexity of Local Search for Weighted Standard Set Problems". CiE 2010: Programs, Proofs, Processes. Lecture Notes in Computer Science. Vol. 6158. Springer, Berlin, Heidelberg. pp. 132–140. CiteSeerX   10.1.1.762.6801 . doi:10.1007/978-3-642-13962-8_15. ISBN   978-3-642-13961-1. S2CID   14099014.
  18. 1 2 Papadimitriou, C.H.; Schäffer, A. A.; Yannakakis, M. (1990). "On the complexity of local search". Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90. pp. 438–445. doi:10.1145/100216.100274. ISBN   0897913612. S2CID   16877206.
  19. 1 2 3 Fabrikant, Alex; Papadimitriou, Christos; Talwar, Kunal (2004). "The complexity of pure Nash equilibria". Proceedings of the thirty-sixth annual ACM symposium on Theory of computing. ACM. pp. 604–612. CiteSeerX   10.1.1.3.7861 . doi:10.1145/1007352.1007445. ISBN   978-1581138528. S2CID   1037326.
  20. 1 2 3 4 5 Ackermann, Heiner; Röglin, Heiko; Vöcking, Berthold (2008). "On the Impact of Combinatorial Structure on Congestion Games". J. ACM. 55 (6): 25:1–25:22. CiteSeerX   10.1.1.634.4913 . doi:10.1145/1455248.1455249. ISSN   0004-5411. S2CID   3070710.
  21. Yang, Yichen; Jia, Kai; Rinard, Martin (2022). "On the Impact of Player Capability on Congestion Games". Algorithmic Game Theory. Lecture Notes in Computer Science. Vol. 13584. pp. 311–328. arXiv: 2205.09905 . doi:10.1007/978-3-031-15714-1_18. ISBN   978-3-031-15713-4.
  22. 1 2 3 4 Dumrauf, Dominic; Monien, Burkhard (2013). "On the PLS-complexity of Maximum Constraint Assignment". Theor. Comput. Sci. 469: 24–52. doi: 10.1016/j.tcs.2012.10.044 . ISSN   0304-3975.
  23. Kaznatcheev, Artem (2019). "Computational Complexity as an Ultimate Constraint on Evolution". Genetics. 212 (1): 245–265. doi:10.1534/genetics.119.302000. PMC   6499524 . PMID   30833289.
  24. Fearnley, John; Goldberg, Paul; Hollender, Alexandros; Savani, Rahul (2022-12-19). "The Complexity of Gradient Descent: CLS = PPAD ∩ PLS". Journal of the ACM. 70 (1): 7:1–7:74. arXiv: 2011.01929 . doi:10.1145/3568163. ISSN   0004-5411. S2CID   263706261.
  25. Yannakakis, Mihalis (2009-05-01). "Equilibria, fixed points, and complexity classes". Computer Science Review. 3 (2): 71–85. arXiv: 0802.2831 . doi:10.1016/j.cosrev.2009.03.004. ISSN   1574-0137.