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:

Use $A_{L}$ to find an initial solution $s$
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.^[1]

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

↑ Fabrikant, Alex; Papadimitriou, Christos; Talwar, Kunal. "The complexity of pure Nash equilibria". STOC '04 Proceedings of the thirty-sixth annual ACM symposium on Theory of computing. ACM: 604-612. doi:10.1145/1007352.1007445. Retrieved 11 June 2017.

PLS (complexity)

References

Further reading