HiveBrain v1.2.0
Get Started
← Back to all entries
principleMinor

Has there been any more progress on P vs. PSPACE compared to P vs. NP?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
comparedanymorepspacebeenhasprogressthere

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#23745, answer score: 9

Revisions (0)

No revisions yet.