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 $\Sigma$. For each instance $x$ there exists a finite solution set $F_L(x)$. Each solution $s \in F_L(x)$ has a non negative integer cost given by a function $c_L(s, x)$ and a neighborhood $N(s, x) \subseteq F_L(x)$. Additionally, the existence of the following three polynomial time algorithms is required:

• Algorithm $A_L$ produces some solution $A_L(x) \in F_L(x)$.
• Algorithm $B_L$ determines the value of $c_L(s, x)$.
• Algorithm $C_L$ maps a solution $s \in F_L(x)$ to an element $s' \in N(s, x)$ such that $c_L(s', x) < c_L(s, x)$ if such an element exists. Otherwise $C_L$ reports that no such element exists.

An instance $D_L$ has the structure of an implicit graph, the vertices being the solutions with two solutions $s, s' \in F_L(x)$ connected by a directed arc iff $s' \in 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 \in F_L(x)$ such that $c_L(s', x) \geq c_L(s, x)$ for all $s' \in 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' \in 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.

References

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