Полиномиалды Жергілікті Іздеу класы (PLS)

Complexity class
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. The main characteristics of problems that lie in PLS are that the cost of a solution can be calculated in polynomial time and the neighborhood of a solution can be searched in polynomial time. Therefore it is possible to verify whether or not a solution is a local optimum in polynomial time. Furthermore, depending on the problem and the algorithm that is used for solving the problem, it might be faster to find a local optimum instead of a global optimum.

A Reduction of one problem to another may be used to show that the second problem is at least as difficult as the first. In particular, a PLS reduction is used to prove that a local search problem that lies in PLS is also PLS complete, by reducing a PLS complete Problem to the one that shall be proven to be PLS complete.

PLS lies between the functional versions of P and NP: FP ⊆ PLS ⊆ FNP. 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 to another. It is also proven that if a PLS problem is NP hard, then NP = co NP.

Fearnley, Goldberg, Hollender and Savani proved that a complexity class called CLS is equal to the intersection of PPAD and PLS.