7

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?

Edit:

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?

Stop Harming the Community
  • 179
  • 3
Anonymous
  • 4,041
  • 19
  • 43
  • 20
    The possibility of L=NP has not been ruled out. – Tsuyoshi Ito Sep 09 '12 at 03:05
  • 1
    @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
  • 3
    Related question: http://cstheory.stackexchange.com/questions/2032/a-decision-problem-which-is-not-known-to-be-in-ph-but-will-be-in-p-if-p-np/2039#2039. 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
  • 1
    To add to Tsuyoshi's comment. I believe that even the possibility of L=PP has not yet been ruled out. – Michael Wehar Apr 08 '15 at 02:32

0 Answers0