On Finding Locally Optimal Solutions (extended abstract)
Mark W. Krentel · 1989
We consider the problem of finding locally optimal solutions to combinatorial problems in the framework of PLS as defined in [JPY88]. We exhibit a PLScomplete problem such that the problem of verifying local optimality can be solved in LOGSPACE. For all previously known PLS-complete problems, verifying local optimality was P-complete, and it was conjectured in [JPY88] that this was necessary.