既然找到局部最优解可能比找到最优解更容易，我们是否可以声称对于任何局部搜索算法，在邻域中进行搜索的一步总是可以在多项式时间内完成？
No.搜索邻域的难易程度取决于邻域的定义方式。
想象一下Max-2SAT问题： 设U是一组二进制变量x_1 、...、x_n并设C是一组子句c在U上 .每个子句中的文字数最多为两个，子句 c∈ C的权重w(c(是正整数。解决方案是x_1、...、x_n的赋值。如果至少有一个变量为 1，则满足子句。 目的是找到一个赋值，使满足条款的权重总和最大化。
设FLIP是邻域结构，其中通过翻转 s 的一位x_i获得解s的邻居r。该邻域具有多项式大小，下一个最佳邻居可以在多项式时间内找到。
设ALL是包含U所有可能解的邻域结构。此邻域具有指数大小，找到下一个最佳邻域(在本例中为全局最优(需要指数级时间。 然后，局部搜索算法在一步后终止，因此它实际上不是一个好的局部搜索算法，而是一个具有指数邻域函数的算法。
还有更复杂的算法具有指数邻域函数，例如在I.A. Davydov，P.A. Kononova，Yu.A.的"服务器负载平衡问题的指数邻域本地搜索"中。科切托夫，2014 年。 它们在所有服务器上所有可能的磁盘子集中用混合整数程序搜索下一个邻居，这些子集是许多可能的邻居的指数级增长。
如果你有一个局部搜索问题，你可以在多项式时间内产生一些解，在多项式时间内计算解的成本，并在多项式时间内找到最佳邻居，你的问题在于复杂度类PLS(参见David S Johnson，Christos H Papadimitriou和Mihalis Yannakakis的"局部搜索有多容易？"， 1988年(。