On the complexity of local search

Abstract

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)