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:

...
Wikipedia