2
$\begingroup$

Accordingly, to the question Chomsky Hierarchy and P vs NP, Context-Sensitive Grammars are on Linear Space.

Assuming a Deterministic Parser is the one which can parse unambiguous grammars in something like linear time complexity, while a NonDeterministic Parser can parse any grammar in some worst time complexity like $O(n^5)$ or exponential.

  1. When something is on Linear Space, it takes Exponential time to be parsed by a Deterministic Parser? (probably space complexity has no relation to its time complexity, maybe something in $NSPACE(n)$ or $PSPACE(n^2)$ can affect time complexity?)
  2. Can any Context Sensitive Grammar be parsed in a Polynomial Complexity Time?
$\endgroup$
  • 2
    $\begingroup$ Please note this site is not for casual chatting. 1) "Context Sensitive Grammar" has nothing to do "Polynomial Complexity Time" (even though I could guess what you meant). 2) Instead of "they say", you are supposed to be specific about who they are. 3) How you defined what "a Determinstic Parser" is? 4) What is your question, actually? What is the "it" in "it means"? Why do you think that "it" means what you said it is supposed to mean. $\endgroup$ – Apass.Jack Jul 7 at 18:09
  • $\begingroup$ You could be much more casual if you are talking to one person without any recording. This question has been viewed 15 times. It is only fair that the question should be well-written and well-thought. It is nice that you have carefully tagged your question. Can you make the question better? Thank you. $\endgroup$ – Apass.Jack Jul 7 at 18:21
  • $\begingroup$ Hi @Apass.Jack, I did some editing. What do you think now? $\endgroup$ – user Jul 7 at 18:52
  • $\begingroup$ It is better now, thanks to your editing. It occurs to me there are still a few loopholes. Let me hope others can join in. $\endgroup$ – Apass.Jack Jul 8 at 0:58
3
$\begingroup$

To your first question, the answer is affirmative:

On one hand, a task that only takes polynomial time can only take polynomial space, and many among them only take linear space, so there definitely exist tasks which take linear space and polynomial time.

On the other hand, that doesn't mean every task that takes linear space takes only polynomial time. However, until now, nobody has been able to prove either way. Even for the hardest problems that take polynomial space, the PSPACE-complete problems, it is not known whether they can be done in polynomial time: we don't know whether PSPACE = P. If you can prove for a single PSPACE-complete problem that it can be done in polynomial time, or that it cannot, you will be famous in computing science forever. In practice, for such problems, we have no better than exponential algorithms.

To answer your second question: parsing context-sensitive grammars is PSPACE-complete, so it takes exponential time in practice; it takes only polynomial time for growing context-sensitive grammars.

$\endgroup$
  • $\begingroup$ What is a growing context-sensitive grammar? $\endgroup$ – Yuval Filmus Jul 9 at 7:01
  • $\begingroup$ That's a link in the Wikipedia article I linked to. I've added a direct link. $\endgroup$ – reinierpost Jul 9 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.