Timeline for What sets are "decidable from competing provers"?
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 29, 2011 at 15:57 | comment | added | Emil Jeřábek | In fact, the argument in Carl's answer above shows that the polynomial-time version of Ricky's class includes all of polynomial hierarchy. On the other hand, it is included in $\mathrm{NEXP}\cap\mathrm{coNEXP}$ since $\mathrm{MIP}=\mathrm{NEXP}$. | |
| Jul 29, 2011 at 15:45 | comment | added | Emil Jeřábek | As far as I can see, $S_2^P$ would correspond to the case where the game is restricted to one round. | |
| Jul 29, 2011 at 15:13 | history | answered | Ryan O'Donnell | CC BY-SA 3.0 |