Timeline for Extending polynomial hierarchy above $\omega$
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Oct 24 at 7:28 | history | suggested | Lucenaposition | CC BY-SA 4.0 |
corrected notation
|
| Oct 24 at 4:18 | review | Suggested edits | |||
| S Oct 24 at 7:28 | |||||
| Sep 29 at 23:30 | vote | accept | Peter Gerdes | ||
| Sep 28 at 16:05 | answer | added | user533847 | timeline score: 4 | |
| Sep 25 at 8:38 | comment | added | Emil Jeřábek | The standard $\Sigma^P_n$-complete problem is QBF restricted to $\Sigma^q_n$ sentences. The natural uniform version of that is, well, QBF. Which is PSPACE-complete, hence again, this takes you to PSPACE already at the $\omega$ level, and then the oracle hierarchy stops as $\mathrm{NP^{PSPACE}=PSPACE}$. The problem remains uniformly hard for all finite levels if you restrict the number of alternations in the QBF by a slower growing function, but then you basically get to the $\Sigma_{a(n)}\mathrm P$ classes as in my answer. | |
| Sep 25 at 1:21 | comment | added | Peter Gerdes | An Oracle for any hard problems in the classes $\Delta^P_n$ should do the trick no? I mean one way of defining the hierarchy is via relativization using oracles (each sigma level is just NP with relative to the Oracle for the previous level). If you can do that uniformly I don't see the problem. | |
| Sep 24 at 9:08 | answer | added | Emil Jeřábek | timeline score: 6 | |
| Sep 24 at 7:58 | comment | added | Gro-Tsen | Just to point out the obvious: in the arithmetic hierarchy, there is a universal/uniform oracle which lets you jump from one level to the next (viꝫ. the halting problem relativized to the previous level). I'm not aware that there's a similar thing for the polynomial hierarchy, so I don't see an obvious way to construct level $\omega$ of the polynomial hierarchy (this does not mean, of course, that it can't be done). | |
| Sep 24 at 7:24 | history | edited | YCor | CC BY-SA 4.0 |
added broad tag, removed capitals
|
| Sep 24 at 3:55 | history | asked | Peter Gerdes | CC BY-SA 4.0 |