If L=P then P is not equal to PSPACE. This follows from PSPACE properly containing L.

I am wondering if L=P implies any stronger separation between complexity classes? Does it imply P is properly contained in NP?


As Tsuyoshi points out, it is consistent with current state of our knowledge that L=NP in which case L=P=NP.

The question can be state more rigorously as improving the result in the first line of this post:

Is there an interesting complexity class C which we don't know if it is separated from L (by the space hierarchy theorem, etc.), however we know that if L=P then L will be strictly contained in C?

  • 19
    $\begingroup$ The possibility of L=NP has not been ruled out. $\endgroup$ Sep 9 '12 at 3:05
  • 1
    $\begingroup$ @Geekster, I am not sure I understood your comment correctly, are you saying that it is not sure that a problem that has a solution in $O(n^2)$, has one in $O(n^3)$? Because it has one: you take the solution that runs in $O(n^2)$, and you add this loop: for $i= 1$ to $n^3$ do nothing done. $\endgroup$
    – Gopi
    Sep 10 '12 at 15:51
  • 3
    $\begingroup$ Related question: cstheory.stackexchange.com/questions/2032/…. I tried modifying my answer to that question to construct a language $A \in PSPACE$ such that if $L = P$ then $A$ is neither in $P$ nor $PSPACE$-complete (hence a stronger separation than $P \neq PSPACE$), but that if $L \neq P$ then $A \in P$. I think this should be doable by combining the ideas there and a Ladner-type construction, but it wasn't immediately obvious to me. $\endgroup$ Nov 21 '12 at 17:58
  • 1
    $\begingroup$ To add to Tsuyoshi's comment. I believe that even the possibility of L=PP has not yet been ruled out. $\endgroup$ Apr 8 '15 at 2:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.