In the definition of the complexity class $\textsf{PLS}$ we have an algorithm for improving the solutions locally. I have come across the following two definition of such an algorithm.

there is a polynomial-time algorithm $C_P$ that, given $x\in\mathcal{I}_P$ and $s\in\mathcal{F}_P(x)$, either outputs a better solution $s'\in \mathcal{N}_P(x,s)$, or reports that $s$ is locally optimal.


there is a polynomial-time algorithm $C'_P$ that, given $x\in\mathcal{I}_P$ and $s\in\mathcal{F}_P(x)$, returns $\mathcal{N}_P(x,s)$.

Here $P$ is a $\textsf{PLS}$ problem, $\mathcal{I}_P$ is a set of instances of $P$, $\mathcal{F}_P(x)$ is a set of feasible solutions of $x\in\mathcal{I}_P$, and $\mathcal{N}_P(x,s)$ is a neighbourhood of $s\in\mathcal{F}_P(x)$.

It is clear that the existence of $C'_P$ implies the existence of $C_P$. Why the existence of $C_P$ implies the existence of $C'_P$?

If it is not the case, could you give me a counterexample? Maybe it could be the case that $\mathcal{N}_P(x,s)$ has an exponential size and we can determine that $s$ is locally optimal by some other property of the instance $x$ or the solution $s$?


1 Answer 1


In general, searching a neighborhood for a better solution and reporting the whole neighborhood are two different things. There are for example some exponential neighborhoods, that is, neighborhoods whose size grows exponentially in the input length $n$, that can be searched in polynomial time for a better solution, see for example A study of exponential neighborhoods for the Travelling Salesman Problem and for the Quadratic Assignment Problem by Deineko and Woeginger. The PLS framework, however, is not so much concerned with the running time of searching the neighborhood but with the number of iterations that are needed to find a locally optimal solution.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.