Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
17  
The possibility of L=NP has not been ruled out. –  Tsuyoshi Ito Sep 9 '12 at 3: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: 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. –  Joshua Grochow Nov 21 '12 at 17:58

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.