The class PLS (Polynomial Local Search) captures the complexity of finding a solution that is locally optimal and has proven to be an important concept in the theory of local search. It has been shown that local search versions of various combinatorial optimization problems, such as Maximum Independent Set and Max Cut, are complete for this class. Such computational intractability typically arises in local search problems allowing arbitrary weights; in contrast, for unweighted problems, locally optimal solutions can be found in polynomial time under standard settings. In this paper, we pursue the complexity of local search problems from a different angle: We show that computing two locally optimal solutions is NP-hard for various natural unweighted local search problems, including Maximum Independent Set, Minimum Dominating Set, Max SAT, and Max Cut. We also discuss several tractable cases for finding two (or more) local optimal solutions.

翻译：PLS（多项式局部搜索）类刻画了寻找局部最优解的复杂度，并已被证明是局部搜索理论中的一个重要概念。研究表明，多种组合优化问题（如最大独立集和最大割）的局部搜索版本对该类具有完备性。这类计算难解性通常出现在允许任意权重的局部搜索问题中；相比之下，对于无权问题，在标准设定下可在多项式时间内找到局部最优解。本文从另一角度探讨局部搜索问题的复杂度：我们证明，对于多种自然的无权局部搜索问题（包括最大独立集、最小支配集、最大可满足性和最大割），计算两个局部最优解是NP难的。我们还讨论了寻找两个（或更多）局部最优解的若干可解情形。