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?

Improve this question
$\endgroup$
3
  • $\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, 2016 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, 2016 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, 2016 at 9:50

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
0
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$.

Improve this answer
$\endgroup$
2
  • $\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, 2016 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$
    – Sarvottamananda
    Mar 31, 2016 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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