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?
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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.
-
1$\begingroup$ 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. $\endgroup$ Commented Apr 13, 2014 at 19:48
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ 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}$. $\endgroup$ Commented Apr 13, 2014 at 22:11
-
$\begingroup$ 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." $\endgroup$ Commented Apr 14, 2014 at 8:25