A PLS problem has a set of instances which are encoded using an 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:
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
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.