On Finding and Verifying Locally Optimal Solutions

The problem of finding locally optimal solutions to combinatorial problems in the framework of PLS as defined by D.S. Johnson, C.H. Papadimitriou, and M. Yannakakis [J. Comput. System Sci., 37(1988), pp. 79–100] is considered. A PLS-complete problem is exhibited 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 [J. Comput. System Sci., 37(1988), pp. 79–100] that this was necessary.