[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 

> 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 :)



Yahoo! Groups Links

To visit your group on the web, go to:

To unsubscribe from this group, send an email to:
 antlr-interest-unsubscribe at yahoogroups.com

Your use of Yahoo! Groups is subject to:

More information about the antlr-interest mailing list