# Are Context Sensitive Grammar with Polynomial Complexity Time?

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?
• 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. – John L. Jul 7 '19 at 18:09
• 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. – John L. Jul 7 '19 at 18:21
• Hi @Apass.Jack, I did some editing. What do you think now? – user Jul 7 '19 at 18:52
• 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. – John L. Jul 8 '19 at 0:58