Timeline for Extending polynomial hierarchy above $\omega$
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 1 at 23:06 | comment | added | Peter Gerdes | Not all reasons to extend the hierarchy are necessarily specifically about classification in the sense you mention. One might, for instance as I was in asking the quesiton, be curious about the potential to find analogs of results in higher computability theory that rely on a non-collapsing hierarchy through some sequence of notations for each ordinal. I'm sorry if you aren't interested in a non-canonical hierarchy but I happen to be. | |
| Sep 30 at 9:40 | comment | added | Emil Jeřábek | So, take a specific problem $L$ in PSPACE whose relation to other classes is not clear, for example, $L$ = the existential theory of the reals. Then if there were an honest transfinite extension of PH, it would be a natural question to ask what is the least $\alpha<\omega_1^{\mathrm{CK}}$ (if any) such that $L$ is on the $\alpha$th level of the hierarchy. This question is totally meaningless for the hierarchy from the paper above, as the levels are defined using arbitrary choices and different choices may yield completely different answers. | |
| Sep 30 at 6:24 | comment | added | Emil Jeřábek | But what's the point of that if the extension is noncanonical? Then it's just a collection of meaningless classes with no connection to classification of the complexity of problems, killing all the original motivation for the definition of PH. I already told you how to do that in my answer, it's trivial: choose an ordinal-indexed sequence of functions $f_\alpha$ (such that $f_{\alpha+1}=f_\alpha+1$ and $f_\alpha$ eventually dominates $f_\beta$ for $\beta<\alpha$; there exists such a sequence of length $\mathfrak b\ge\omega_1$), and put $\Sigma_\alpha^P:=\Sigma_{f_\alpha}\mathrm P$. | |
| Sep 29 at 23:35 | comment | added | Peter Gerdes | Yes, you are right that wasn't a very good explanation and probably the wrong intuition. But it's kinda besides the point since the article given below shows that you can meaningfully extend the hierarchy to higher ordinal notations but it's not a very nice extension in that it's non-unique. | |
| Sep 25 at 5:30 | comment | added | Emil Jeřábek | I don't understand what you mean. The number of alternations is a priori polynomially bounded as the overall running time is polynomially bounded. If the machine can choose the bound at will, it can simply choose a sufficiently large polynomial already at the $\omega$ level. Thus, you get PSPACE at level $\omega$ and the hierarchy collapses to that level. | |
| Sep 25 at 1:30 | comment | added | Peter Gerdes | For instance consider how the w-re sets are defined... though it would be a bit more complicated. | |
| Sep 25 at 1:28 | comment | added | Peter Gerdes | I'd think the natural thing to do at $\omega$ would be to insist that the alternations are in some sense assigned a decreasing sequence of naturals (so in general you get a sequence choose from the ordinal level in question). That's not finitely bounded but there will be a difference between ordinal levels, e.g. at w the machine has to declare it will use only n alterations for each instance immediately. At w^2 the machine gets to pick a number of alterations before it hits w at which point it gets to pick how many alterations it will use below that and so on. | |
| Sep 24 at 10:08 | comment | added | Emil Jeřábek | Funnily enough, I finally got a silver set-theory tag badge for an answer that has nothing to do whatsoever with set theory. | |
| Sep 24 at 9:08 | history | answered | Emil Jeřábek | CC BY-SA 4.0 |