Timeline for What sets are "decidable from competing provers"?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 29, 2011 at 1:26 | comment | added | Carl Mummert | I will fix the notation $0^{(a)}$ the next time I edit the question. The preview broke when I was writing it. | |
| Jul 29, 2011 at 1:24 | comment | added | Carl Mummert | @Kaveh: the idea of $0^{\omega}$ occurred to me as well, I was writing it up at the same time you commented. I don't yet see how to give a full characterization, though. Because the oracles can give any natural number as output, quantifying over wining strategies seems difficult. | |
| Jul 29, 2011 at 1:22 | comment | added | Kaveh | It seems to me that you can do this uniformly also since the number of alternations can depend on n, i.e. the class contains the truth predicate for arithmetic formulas, and the reverse also holds so I think the answer is the class is $(\Delta^1_0)′$. Also TM not halting does not change the class. | |
| Jul 29, 2011 at 1:22 | history | edited | Carl Mummert | CC BY-SA 3.0 |
added 928 characters in body
|
| Jul 29, 2011 at 1:06 | history | answered | Carl Mummert | CC BY-SA 3.0 |