Polynomial hierarchy infinitude

Choosing once and choosing after seeing somebody else’s move are different tasks. Suppose each player chooses either 0 or 1, and you must match the other player. No choice you make first works against both possibilities. If you choose second, you can always match. Computation has a similar distinction between “there is a choice that works for every reply” and “for every reply there is a suitable choice.” The polynomial hierarchy asks whether adding another alternating layer of these questions always allows more decision problems to be expressed.[1] [3]

The polynomial hierarchy measures the complexity of nested choices with an efficient final check. Its open infinitude question asks whether every additional fixed level strictly enlarges the class of decision problems. Write $\exists$ for “there exists” and $\forall$ for “for every.” For bits, $\exists x\,\forall y\;(x=y)$ is false, whereas $\forall y\,\exists x\;(x=y)$ is true: the later choice may depend on the earlier one. At level $\Sigma_k^{\mathrm P}$, the choices are polynomial-length strings arranged in $k$ alternating blocks beginning with $\exists$, followed by a deterministic polynomial-time test. Set $\Sigma_0^{\mathrm P}=\mathrm P$; then $\Sigma_1^{\mathrm P}=\mathrm{NP}$. The target is $\Sigma_k^{\mathrm P}\subsetneq\Sigma_{k+1}^{\mathrm P}$ for every fixed $k\geq0$. The two-bit example explains quantifier order; it proves no class separation.[1] [3]

The endless ladder is conjectured, but not proved for ordinary computation.[1] [2] [3]

Infinitude relative to random or constructed oracles does not imply infinitude without an oracle.[1] [2] [3]

A candidate solution may need to withstand every attempted counterexample; a response to a counterexample may itself need another check. These are different logical demands from merely exhibiting one successful candidate. The hierarchy studies whether an unlimited sequence of such fixed layers creates genuinely different capabilities, or whether all these nested questions eventually compress into a single finite level.[1] [3]

An equality between adjacent levels would collapse the entire hierarchy to a finite level: every fixed-depth pattern could then be expressed there. Infinitude would instead establish that no finite level captures all such patterns. This connects local choices of quantifier order to the global organization of decision problems, including statements that a candidate exists and that all alternatives fail. The number of alternating blocks is fixed for each level; it is not allowed to grow with the input.[1] [3]