PLS (complexity)

In computational complexity theory, PLS, which stands for Polynomial Local Search, is a complexity class that models the difficulty of finding a locally optimal solution to an optimization problem.

An instance of PLS has the structure of an implicit graph, defined by a polynomial-time algorithm for computing the neighbors of each vertex in the graph, together with another polynomial-time algorithm for computing a cost for each vertex. A valid solution to the instance is a vertex v in the graph for which no neighbor of v has smaller cost. If there is more than one such vertex, they are all valid.

Examples of PLS-complete problems include local-optimum relatives of the travelling salesman problem, maximum cut and satisfiability, as well as finding a pure Nash equilibrium in a congestion game.

PLS is a subclass of TFNP, a complexity class closely related to NP 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.

References

• Yannakakis, Mihalis (2009), "Equilibria, fixed points, and complexity classes", Computer Science Review, 3 (2), Elsevier: 71–85.