Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
The possibility of L=NP has not been ruled out. – Tsuyoshi Ito Sep 9 '12 at 3:05
@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. – Gopi Sep 10 '12 at 15:51
Related question:…. 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. – Joshua Grochow Nov 21 '12 at 17:58
To add to Tsuyoshi's comment. I believe that even the possibility of L=PP has not yet been ruled out. – Michael Wehar Apr 8 '15 at 2:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.