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

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

<p>Edit:</p>

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

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

<blockquote>
  <p>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? </p>
</blockquote>

CC BY-SA 3.0
2012-09-09T03:05:15.120Z
The possibility of L=NP has not been ruled out.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-10T15:51:50.883Z
@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
CC BY-SA 3.0
2012-11-21T17:58:00.053Z
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
CC BY-SA 3.0
2015-04-08T02:32:16.890Z
To add to Tsuyoshi's comment.  I believe that even the possibility of L=PP has not yet been ruled out.
Michael Wehar
<cc.complexity-theory><time-complexity><p-vs-np><conditional-results><space-complexity>
Does L=P imply any new complexity class separations?
Anonymous
# Does L=P imply any new complexity class separations?

(Asked by: username_0 on 2012-09-09)

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?

**Tags:** cc.complexity-theory, time-complexity, p-vs-np, conditional-results, space-complexity
> **Comments:**
> **username_1**: The possibility of L=NP has not been ruled out.  
> **username_2**: @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.  
> **username_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.  
> **username_4**: To add to Tsuyoshi's comment.  I believe that even the possibility of L=PP has not yet been ruled out.  

---

## 0 answers

