Structure in locally optimal solutions
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 216-221
- https://doi.org/10.1109/sfcs.1989.63481
Abstract
A class of local search problems, PLS (polynomial-time local search), as defined by D.S. Johnson et al. (see J. Comput. Syst. Sci., vol.37, no.1, p.79-100 (1988)) is considered. PLS captures much of the structure of NP problems at the level of their feasible solutions and neighborhoods. It is first shown that CNF (conjunctive normal form) satisfiability is PLS-complete, even with simultaneously bounded size clauses and bounded number of occurrences of variables. This result is used to show that traveling salesman under the k-opt neighborhood is also PLS-complete. It is argued that PLS-completeness is the normal behavior of NP-complete problems.Keywords
This publication has 5 references indexed in Scilit:
- On Finding and Verifying Locally Optimal SolutionsSIAM Journal on Computing, 1990
- How easy is local search?Journal of Computer and System Sciences, 1988
- The complexity of optimization problemsJournal of Computer and System Sciences, 1988
- On the complexity of unique solutionsJournal of the ACM, 1984
- An Efficient Heuristic Procedure for Partitioning GraphsBell System Technical Journal, 1970