Title :
Structure in locally optimal solutions
Author_Institution :
Dept. of Comput. Sci., Rice Univ., Houston, TX
fDate :
30 Oct-1 Nov 1989
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 :
computational complexity; search problems; NP problems; PLS; conjunctive normal form; local search problems; locally optimal solution structure; polynomial-time local search; traveling salesman; Circuits; Computer science; Cost function; NP-complete problem; Partitioning algorithms; Polynomials; Search problems;
Conference_Titel :
Foundations of Computer Science, 1989., 30th Annual Symposium on
Conference_Location :
Research Triangle Park, NC
Print_ISBN :
0-8186-1982-1
DOI :
10.1109/SFCS.1989.63481