<p>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 href="http://link.springer.com/article/10.1007/s101070050010" rel="nofollow noreferrer">A study of exponential neighborhoods for the Travelling Salesman Problem and for the Quadratic Assignment Problem</a> 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.</p>

CC BY-SA 3.0
2017-01-12T09:09:13.087Z
2017-01-12T09:09:13.087Z
Christian Komusiewicz
<p>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. </p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>and</p>

<blockquote>
  <p>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)$.</p>
</blockquote>

<p>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)$.</p>

<p>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$? </p>

<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$?</p>

<cc.complexity-theory><complexity-classes><complexity><equivalence>
Why are these two definitions of PLS equivalent?
Andrius Vaicenavicius
# Why are these two definitions of PLS equivalent?

(Asked by: username_0 on 2017-01-11)

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.

and

> 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$?

**Tags:** cc.complexity-theory, complexity-classes, complexity, equivalence

---

## 1 answers

### Answer by username_1 on 2017-01-12. Score: 2 | Accepted answer

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](http://link.springer.com/article/10.1007/s101070050010) 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.


---

