On the complexity of local search
Christos H. Papadimitriou, Alejandro A. Schäffer, Mihalis Yannakakis · 1990
We prove a number of complexity results on the computational paradigm of local optimality.Our main results are these: (a) Finding a local optimum under the Lin-Kernighan heuristic for the traveling salesman problemis PLS-complete.(b) Finding stable configurations in neural networks in the Hopfield mode/is PLS-complete.(c) We show that a host of simple unweighted local optimality problems are P-complete.(d) We introduce a general framework for establishing exponential worstcase bounds for local optimization heuristics.(e)And we show that local search problems become PSPACE-complete if we insist that the local optimum returned be attainable by local improvements from a given initial solution.In [JPY] two problems were shown to be PLScomplete and thus as hard as any problem in PLS; they were a "generic" problem called FLIP, and the problem of finding a local optimum in the Kernighan-Lin heuristic for the graph partitioning problem [KL].