Timeline for Has there been any more progress on P vs. PSPACE compared to P vs. NP?
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 14, 2014 at 8:25 | comment | added | Thomas Klimpel | 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." | |
| Apr 13, 2014 at 22:11 | comment | added | Thomas Klimpel | 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}$. | |
| Apr 13, 2014 at 22:02 | history | answered | Thomas Klimpel | CC BY-SA 3.0 |