# Is it true that P is not equal to deterministic linear space complexity class?

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?

• @AndrásSalamon Am I missing something? I don't see the relevance of the question you're suggesting this duplicates -- that's a question about bounding functions and this is a question about whether a space complexity class is equal to a time class. Apr 1 '16 at 0:00
• Hmm, the question I was suggesting as a duplicate is not the one the system recorded. Apr 1 '16 at 9:44
• The question Yuval pointed to mathoverflow.net/questions/40770/… is a clear duplicate of this one, with several comprehensive answers. Apr 1 '16 at 9:50

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.
We know that $DSPACE(n) \neq NP$ (we only know they are unequal, we don't even know if one is a subset of other or not).
We also know that $DTIME(n) \subseteq DSPACE(n) \subseteq NSPACE(n) \subseteq DTIME(2^{O(n)})$.
As Yuval Filmus pointed out $DSPACE(n) \neq P$.
• $DSPACE$ and $P$ are complexity classes, ie, they are about problems and not about algorithms as such. So there may exist a problem which has both a DSPACE(n) algorithm and another polynomial time algorithm. What is not known is if a DSPACE(n) algorithm solves a problem, do we also have a polynomial time algorithms for the same problem and vice versa. Mar 31 '16 at 13:45