The class PLS

From: Blake Manner (cnglover_at_wam.umd.edu)
Date: 11/18/04 

Date: 17 Nov 2004 16:41:43 -0800

I am a graduate student in mathematics who is currently trying to read
a paper by David Johnson, Christos Papadimitriou, and Mihalis
Yannakakis entitled "How Easy is Local Search". I'm having a bit of a
problem understanding what the class of problems, PLS is.

I realize that its a set of ordered pair (x, y), where y is a locally
optimal solution to x.

"R = {(x, y) | x [belongs to] D<sub>L</sub> and y [belongs to]
F<sub>L</sub>(x) and is locally optimal}"

So there is some local search which on input x outputs y. But contrary
to the name of PLS (polynomial time local search), this local search
does not need to halt in polynomial amount of time?

This puzzles me because in the paper, there is a proof that there is a
problem in PLS with the same instances as SAT. They prove that its in
PLS by providing an algorithm that goes through all possible
satisfying assignments until one is reached. Why couldn't this same
reasoning imply that any NP problem was in PLS, and thus that PLS =
NP<sub>S</sub>.

Because I have seen this class mentioned 3 times on this message
board, I realize that this is not as simple as I'm making it. However,
I am curious to know what I am misunderstanding from this problem. If
anyone can help me, I would really appreciate it.

Charles N. Glover