On finding locally optimal solutions
Mark W. Krentel · 2003
The problem of finding locally optimal solutions to combinatorial problems in the framework of polynomial-time local search as defined by D.S. Johnson et al. (J. Comput. Syst. Sci., vol.37, no.1, p.79-100, Aug. 1988) is considered. A PLS-complete problem such that the problem of verifying local optimality can be solved in LOGSPACE is exhibited. For all previously known PLS-complete problems, verifying local optimality was P-complete, and it was conjectured in Johnson et al. that this was necessary.>