3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – David Richerby Apr 1 '16 at 0:00
  • $\begingroup$ Hmm, the question I was suggesting as a duplicate is not the one the system recorded. $\endgroup$ – András Salamon Apr 1 '16 at 9:44
  • $\begingroup$ The question Yuval pointed to mathoverflow.net/questions/40770/… is a clear duplicate of this one, with several comprehensive answers. $\endgroup$ – András Salamon Apr 1 '16 at 9:50
5
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thanks Shrees. So this means that there is no such known algorithm which is P but not DSPACE or is DSPACE but not P? $\endgroup$ – Milano Mar 31 '16 at 8:49
  • 1
    $\begingroup$ $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. $\endgroup$ – Shreesh Mar 31 '16 at 13:45

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.