A PLS problem has a set of instances which are encoded using strings over a finite alphabet . For each instance there exists a finite solution set . Each solution has a non negative integer cost given by a function and a neighborhood . Additionally, the existence of the following three polynomial time algorithms is required:
- Algorithm produces some solution .
- Algorithm determines the value of .
- Algorithm maps a solution to an element such that if such an element exists. Otherwise reports that no such element exists.
An instance has the structure of an implicit graph, the vertices being the solutions with two solutions connected by a directed arc iff . The most interesting computational problem is the following:
Given some instance of a PLS problem , find a local optimum of , i.e. a solution such that for all
The problem can be solved using the following algorithm:
- Use to find an initial solution
- Use algorithm to find a better solution . If such a solution exists, replace by , else return
Unfortunately, it generally takes an exponential number of improvement steps to find a local optimum even if the problem can be solved exactly in polynomial time.
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.
- 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.
|P ≟ NP||This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.|