# 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 ${\displaystyle L}$ has a set ${\displaystyle D_{L}}$ of instances which are encoded using strings over a finite alphabet ${\displaystyle \Sigma }$. For each instance ${\displaystyle x}$ there exists a finite solution set ${\displaystyle F_{L}(x)}$. Each solution ${\displaystyle s\in F_{L}(x)}$ has a non negative integer cost given by a function ${\displaystyle c_{L}(s,x)}$ and a neighborhood ${\displaystyle N(s,x)\subseteq F_{L}(x)}$. Additionally, the existence of the following three polynomial time algorithms is required:

• Algorithm ${\displaystyle A_{L}}$ produces some solution ${\displaystyle A_{L}(x)\in F_{L}(x)}$.
• Algorithm ${\displaystyle B_{L}}$ determines the value of ${\displaystyle c_{L}(s,x)}$.
• Algorithm ${\displaystyle C_{L}}$ maps a solution ${\displaystyle s\in F_{L}(x)}$ to an element ${\displaystyle s'\in N(s,x)}$ such that ${\displaystyle c_{L}(s',x) if such an element exists. Otherwise ${\displaystyle C_{L}}$ reports that no such element exists.

An instance ${\displaystyle D_{L}}$ has the structure of an implicit graph, the vertices being the solutions with two solutions ${\displaystyle s,s'\in F_{L}(x)}$ connected by a directed arc iff ${\displaystyle s'\in N(s,x)}$. The most interesting computational problem is the following:

Given some instance ${\displaystyle x}$ of a PLS problem ${\displaystyle L}$, find a local optimum of ${\displaystyle c_{L}(s,x)}$, i.e. a solution ${\displaystyle s\in F_{L}(x)}$ such that ${\displaystyle c_{L}(s',x)\geq c_{L}(s,x)}$ for all ${\displaystyle s'\in N(s,x)}$

The problem can be solved using the following algorithm:

1. Use ${\displaystyle A_{L}}$ to find an initial solution ${\displaystyle s}$
2. Use algorithm ${\displaystyle C_{L}}$ to find a better solution ${\displaystyle s'\in N(s,x)}$. If such a solution exists, replace ${\displaystyle s}$ by ${\displaystyle s'}$, else return ${\displaystyle s}$

Unfortunately, it generally takes an exponential number of improvement steps to find a local optimum even if the problem ${\displaystyle 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.