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.
A PLS problem
An instance
Given some instance
The problem can be solved using the following algorithm:
- Use
A L s - Use algorithm
C L s ′ ∈ N ( s , x ) . If such a solution exists, replaces bys ′ s
Unfortunately, it generally takes an exponential number of improvement steps to find a local optimum even if the problem
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.