Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. 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

I understand this is a slightly vague question, but there are results for P vs. NP, such as the question cannot be easily resolved using oracles. Are there any results like this which have been shown for P vs. NP but have not been shown for P vs PSPACE, so that there is hope that certain proof techniques might resolve P vs PSPACE even though they cannot resolve P vs NP? And are there any non-trivial results that say that if P = PSPACE then there are implications that do not necessarily hold under P = NP? Or anything else non-trivial in the literature that suggests it's easier to prove P != PSPACE than it is to prove P != NP?

share|cite|improve this question
seems like a fair/reasonable question but in some ways all open conjectures are equally difficult... there is really no plausible way to measure "progress" on any conjecture... "work" in theoretical fields is not analogous to "work" in other applied fields. some problems have huge work and no progress and others have small but pivotal work leading to a breakthrough. etc. ... it has a highly nonlinear/unpredictable/assymetric aspect.... – vzn Apr 13 '14 at 22:17
Perhaps this is more suitable for cstheory. – Yuval Filmus Apr 14 '14 at 1:40

To prove that $\mathsf{NP}^A=\mathsf{coNP}^A$ for a "sufficiently natural" $\mathsf{PSPACE}$ oracle $A$ implies $\mathsf{NP}^A=\mathsf{PSPACE}$ should be much easier than to prove $\mathsf{P}\neq\mathsf{PSPACE}$. By "sufficiently natural", I'm especially thinking about languages complete for a certain level of the polynomial hierarchy. Nailing down the exact naturality conditions would be part of proving such a statement.

There are some reasons to believe that such a theorem should exist. We already can prove that $\mathsf{NP}^A=\mathsf{coNP}^A$ for some $\mathsf{PH}$ oracle $A$ leads to the collapse of the polynomial hierarchy at $\mathsf{PH}=\mathsf{NP}^A$. The difference between $\mathsf{PH}$ and $\mathsf{PSPACE}$ in descriptive complexity theory is so small, that it is hard to imagine how the polynomial hierarchy could collapse without also affecting $\mathsf{PSPACE}$. A more subtle reason to believe this which also hints at a strategy for a proof is that $\mathsf{NP}^A$ is closed under finite intersections and nearly arbitrary (=PSPACE bounded) unions.

share|cite|improve this answer
I know this is a problematic answer in certain aspects, but it should explain why we don't really expect $\mathsf{P}\neq\mathsf{PSPACE}$ to be much easier to prove than $\mathsf{P}\neq\mathsf{NP}$. – Thomas Klimpel Apr 13 '14 at 22:11
As a note of caution, we have the following theorem: "There exists $A \subseteq \{0, 1\}^∗$, such that $\mathsf{PH}^A \neq \mathsf{PSPACE}^A$. More generally, for each $k$ there exists an oracle, relative to which the polynomial hierarchy has exactly $k$ levels." – Thomas Klimpel Apr 14 '14 at 8:25

This doesn't really answer your question, but there is a result that under a restricted form of time travel (yes, time travel), it holds that $P=PSPACE$. I'll remark that the result is nontrivial, given the restrictions on the model. See this explanation by Scott Aaronson.

share|cite|improve this answer
That's very interesting, thanks for the link. We'll see what happens with my question but I have a feeling that the answer will be a sad "No", we aren't really any significantly further along proving P != PSPACE than we are proving P != NP. – user2566092 Apr 13 '14 at 19:48

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.