PLS (complexity)

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 L has a set D L of instances which are encoded using strings over a finite alphabet Σ . For each instance x there exists a finite solution set F L ( x ) . Each solution s ∈ F L ( x ) has a non negative integer cost given by a function c L ( s , x ) and a neighborhood N ( s , x ) ⊆ F L ( x ) . Additionally, the existence of the following three polynomial time algorithms is required:

An instance D L has the structure of an implicit graph, the vertices being the solutions with two solutions s , s ′ ∈ F L ( x ) connected by a directed arc iff s ′ ∈ N ( s , x ) . The most interesting computational problem is the following:

Given some instance x of a PLS problem L , find a local optimum of c L ( s , x ) , i.e. a solution s ∈ F L ( x ) such that c L ( s ′ , x ) ≥ c L ( s , x ) for all s ′ ∈ N ( s , x )

The problem can be solved using the following algorithm:

1. Use A L to find an initial solution s
2. Use algorithm C L to find a better solution s ′ ∈ N ( s , x ) . If such a solution exists, replace s by s ′ , else return s

Unfortunately, it generally takes an exponential number of improvement steps to find a local optimum even if the problem L can be solved exactly in polynomial time.

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.