[antlr-interest] Re: Nondeterminism problem

[Oliver Zeigermann]

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/