patternMinor
Is it true that P is not equal to deterministic linear space complexity class?
Viewed 0 times
linearspaceclassequaltruethatdeterministicnotcomplexity
Problem
I'm curious, how could I know that P (polynomial time complexity class) is not equal to deterministic linear space complexity class?
Is there some proof? Or should I find some algorithm which is not in P but it is in polynomial time complexity class or opposite way?
Do you know about some?
Is there some proof? Or should I find some algorithm which is not in P but it is in polynomial time complexity class or opposite way?
Do you know about some?
Solution
We do know that $\mathsf{P} \neq \mathsf{DSPACE}(n)$. This is proved in answers to a question on Mathoverflow. The idea is that $\mathsf{P}$ is closed under polynomial blowup while $\mathsf{DSPACE}(n)$ isn't (due to the space hierarchy theorem); consult the link on Mathoverflow for the details.
Context
StackExchange Computer Science Q#55226, answer score: 5
Revisions (0)
No revisions yet.