6
$\begingroup$

The arithmetic hierarchy is naturally extended to all ordinals via ordinal notations creating a hierarchy for all hyperarithmetic sets. The polynomial time hierarchy is defined analogously to the arithmetic hierarchy but I've never seen it extended into the transfinite.

Given that every ordinal below $\omega_1^{CK}$ is the height of some polynomial time relation does it make sense to extend the polynomial time hierarchy to the transfinite or does something fundamentally break? If so what? Does it collapse after level $\omega$? Or is this a thing and I just haven't heard of it?

--

It seems like one could just define a polynomial time ordinal notation and use that to define a polynomial time analog to the sets $0^\alpha$ but I'm interested in any natural way of extending the analogy. 

$\endgroup$
3
  • $\begingroup$ 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). $\endgroup$
    – Gro-Tsen
    Commented Sep 24 at 7:58
  • $\begingroup$ 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. $\endgroup$ Commented Sep 25 at 1:21
  • $\begingroup$ 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. $\endgroup$ Commented Sep 25 at 8:38

2 Answers 2

4
$\begingroup$

This question was studied in Hyper-polynomial Hierarchies and the NP-jump by Fenner, Homer, Pruim and Schaefer.

$\endgroup$
1
  • $\begingroup$ Thanks, that's exactly what I was looking for! $\endgroup$ Commented Sep 29 at 23:36
6
$\begingroup$

The coherent way of extending the polynomial hierarchy is not indexed by ordinals, but by functions $a\colon\mathbb N\to\mathbb N$: $$\Sigma_{a(n)}\mathrm P=\bigcup_{c\in\mathbb N}\Sigma_{a(n)}\text-\mathrm{TIME}(n^c)$$ is the class of problems computable by a polynomial-time alternating Turing machine that starts in an existential state and makes at most $a(n)-1$ alternations, where $n$ is the length of the input. (This agrees with the usual definition of the polynomial hierarchy when $a$ is a constant.)

When $a$ is an increasing function, one additional alternation hardly matters, while the class $\Sigma_{a(n)}\mathrm P$ will be quite fragile as any kind of operation will likely increase $a$. For this matter, in this context you are more likely to find more robust classes defined by a set of $a$ of certain growth, such as $\Sigma_{O(\log n)}\mathrm P$. Then it is no longer relevant what state you start with, so such classes are more commonly denoted in the literature by something like $$\mathrm{TimeAlternations}(t(n),a(n)),$$ e.g., $\mathrm{TimeAlternations}(n^{O(1)},O(\log n))$, where the resource bound now simply counts the number of alternations.

Unrestricted alternating polynomial time $\mathrm{AP}=\Sigma_\infty\mathrm P=\Sigma_{n^{O(1)}}\mathrm P$ equals PSPACE, so that’s where it stops.

These classes are considered rather rarely, as there are next to no natural situations where they arise. Even inside the usual polynomial hierarchy, you hardly ever encounter problems outside, say, $\Sigma_2^P\cup\Pi_2^P$. There are many interesting complexity classes between PH and PSPACE, but they are defined in different ways than by bounding the number of alternations: typically, they are variants of counting classes, where the decision is made based on the number of accepting paths of the Turing machine. See the basic counting classes PP (wp, zoo) and #P (wp, zoo; this is a class of function problems rather than decision problems), the modular counting classes $\oplus\mathrm P$ (wp, zoo) and more generally $\mathrm{Mod}_p\mathrm P$ (zoo), the counting hierarchy CH (wp, zoo) and modular counting hierarchy ModPH (zoo) (for a fixed prime $p$, the more basic hierarchy $\mathrm{Mod}_p\mathrm{PH}$ collapses to $\mathrm{BP\cdot Mod}_p\mathrm P$ by Toda’s theorem), and various related classes such as MP (zoo).

Anyway, if you try to define a hierarchy indexed by ordinals, it’s quite unclear what to do already at the $\omega$ level. To make it a “limit” of the constant-$k$ $\Sigma_k\mathrm P$ classes, it should allow an unbounded number of quantifiers/alternations, i.e., it should be something like $\Sigma_{a(n)}\mathrm P$ for a suitable function (or a set of functions) $a$, but which one? Different choices yield different classes. (Arguably, the most natural choice, which corresponds to a most obvious way of “diagonalizing” the PH levels, would be to allow polynomial number of alternations, in which case the $\omega$th level is PSPACE and the hierarchy stops.) Furthermore, whatever choice you take, level $\omega+1$ should add one more existential quantifier in front, which just increases $a(n)$ to $a(n)+1$. If you define level $\omega$ using a robust set of functions rather than a single one, this might simply be the same class; either way, it is a class of the same kind as level $\omega$, extept for the, quite arbitrary, choice of the function $a$. If you try to continue to define an ordinal-indexed hierarchy in this way, you will end up with something like $\Sigma_{f_\alpha(n)}\mathrm P$ for an ordinal-indexed family of functions $f_\alpha(n)$, for which there are no natural or canonical choices. In the end, the only robust way to do this is to abandon ordinals and just consider the classes $\Sigma_{a(n)}\mathrm P$ directly.

$\endgroup$
8
  • 4
    $\begingroup$ Funnily enough, I finally got a silver set-theory tag badge for an answer that has nothing to do whatsoever with set theory. $\endgroup$ Commented Sep 24 at 10:08
  • $\begingroup$ 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. $\endgroup$ Commented Sep 25 at 1:28
  • $\begingroup$ For instance consider how the w-re sets are defined... though it would be a bit more complicated. $\endgroup$ Commented Sep 25 at 1:30
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Sep 25 at 5:30
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Oct 1 at 23:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .