Timeline for What are examples of complexity classes that have contradictory relativizations but they were proven to be either equal or unequal?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 31, 2017 at 1:01 | history | tweeted | twitter.com/StackCSTheory/status/903060034187382784 | ||
| Aug 30, 2017 at 19:41 | answer | added | Mal | timeline score: 0 | |
| Aug 30, 2017 at 16:22 | vote | accept | Mal | ||
| Aug 30, 2017 at 16:05 | answer | added | Joshua Grochow | timeline score: 7 | |
| Aug 30, 2017 at 15:04 | comment | added | Mal | Thank you! The Fortnow-Sipser article is very helpful. And you are right, the questions are similar but I wouldn't say they are equal. For example, I have not been able to find an oracle relative to which $\mathsf{MIP}$ and $\mathsf{NEXP}$ are unequal, and it is these sort of oracle results that I am interested in. | |
| Aug 29, 2017 at 15:55 | comment | added | Joshua Grochow | If you just want an oracle where $\mathsf{IP} \neq \mathsf{PSPACE}$, it goes back to Fortnow-Sipser '88, who gave an oracle relative to which $\mathsf{IP}$ didn't even contain $\mathsf{coNP}$. Your question is essentially the same as asking for non-relativizing techniques that have been used to resolve complexity class (in)equalities; see, e.g., this, this, this, or this. | |
| Aug 29, 2017 at 14:22 | history | asked | Mal | CC BY-SA 3.0 |