[antlr-interest] Re: Nondeterminism problem
Oliver Zeigermann
oliver at zeigermann.de
Wed Dec 24 14:25:40 PST 2003
sarah2geller wrote:
> Clearly, if SLK could solve an NP-complete problem in polynomial
> time, that would constitute a proof that P=NP. But the conjecture
> given is that P!=NP, so it seems that you misread something.
Not quite sure, let's do it step by step, quoting from the beginning of
http://home.earthlink.net/~parsersinc/doc/conjecture.html:
> The complexity of testing context-free grammars for the SLL(k) property
> was first investigated by Hunt, Szymanski, and Ullman (1975). They
> showed that the problem is solvable in polynomial time if the value of k is fixed ahead of time.
> That is, if k is not a parameter of the problem, then SLL(k) recognition
> is in P, the class of problems solvable in polynomial time.
Which from my understanding is clearly false as this article *at most*
proves it is in NP as the lower bound estimation was for
"non-deterministic" time. This is because for a "non-deterministic" TM
it is polynomial time, thus the lower bound is clearly in *NP*, not *P*.
Do you agree? Maybe I am missing something, can you see what this might be?
Thanks in advance and cheers :)
Oliver
Yahoo! Groups Links
To visit your group on the web, go to:
http://groups.yahoo.com/group/antlr-interest/
To unsubscribe from this group, send an email to:
antlr-interest-unsubscribe at yahoogroups.com
Your use of Yahoo! Groups is subject to:
http://docs.yahoo.com/info/terms/
More information about the antlr-interest
mailing list