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.

When searching for a local optimum, there are two interesting issues to deal with: First how to find a local optimum, and second how long it takes to find a local optimum. For many local search algorithms, it is not known, whether they can find a local optimum in polynomial time or not. So to answer the question of how long it takes to find a local optimum, Johnson, Papadimitriou and Yannakakis introduced the complexity class PLS in their paper "How easy is local search?". It contains local search problems for which the local optimality can be verified in polynomial time.

A local search problem is in PLS, if the following properties are satisfied:

With these properties, it is possible to find for each solution ${\displaystyle s}$ the best neighboring solution or if there is no such better neighboring solution, state that ${\displaystyle s}$ is a local optimum.

Consider the following instance ${\displaystyle I}$ of the Max-2Sat Problem: ${\displaystyle (x_{1}\vee x_{2})\wedge (\neg x_{1}\vee x_{3})\wedge (\neg x_{2}\vee x_{3})}$. The aim is to find an assignment, that maximizes the sum of the satisfied clauses.

A solution ${\displaystyle s}$ for that instance is a bit string that assigns every ${\displaystyle x_{i}}$ the value 0 or 1. In this case, a solution consists of 3 bits, for example ${\displaystyle s=000}$, which stands for the assignment of ${\displaystyle x_{1}}$ to ${\displaystyle x_{3}}$ with the value 0. The set of solutions ${\displaystyle F_{L}(I)}$ is the set of all possible assignments of ${\displaystyle x_{1}}$, ${\displaystyle x_{2}}$ and ${\displaystyle x_{3}}$.

The cost of each solution is the number of satisfied clauses, so ${\displaystyle c_{L}(I,s=000)=2}$ because the second and third clause are satisfied.

The Flip-neighbor of a solution ${\displaystyle s}$ is reached by flipping one bit of the bit string ${\displaystyle s}$, so the neighbors of ${\displaystyle s}$ are ${\displaystyle N(I,000)=\{100,010,001\}}$ with the following costs: