Bounded alternation qbf is level complete

Given: the objects and hypotheses in the statement above.

All languages are subsets of $\{0,1{\}}^{\ast }$. Put ${\mathrm{\Sigma }}_0^p={\mathrm{\Pi }}_0^p=P$ as in the stated convention. For a fixed integer $k\ge 1$, $L\in {\mathrm{\Sigma }}_k^p$ means that a deterministic polynomial-time predicate $R$ and polynomially bounded, polynomial-time computable lengths $p_1,\dots ,p_k$ satisfy $x\in L⟺\mathrm{\exists }{y}_1\in \{0,1{\}}^{p_1(\mathrm{\mid }x\mathrm{\mid })}\mathrm{\forall }{y}_2\in \{0,1{\}}^{p_2(\mathrm{\mid }x\mathrm{\mid })}\cdots Q_k{y}_k\in \{0,1{\}}^{p_k(\mathrm{\mid }x\mathrm{\mid })}R(x,y_1,\dots ,y_k)\mathrm{.}$ Here $Q_j$ is existential for odd $j$ and universal for even $j$. Starting universally defines ${\mathrm{\Pi }}_k^p$. Write $\mathrm{P}\mathrm{H}={\bigcup }_{k\ge 0}{\mathrm{\Sigma }}_k^p$. The level and all polynomials are fixed for a language, not part of the input. Length zero allows the single empty string. Variable-length witnesses can be encoded with a length field and padding; every padded string decodes to a bounded-length string, so universal blocks introduce no invalid-witness exception. (Polynomial hierarchy levels).

For a fixed polynomial-time Boolean predicate $R(x,y)$, and a polynomial bound on $\mathrm{\mid }y\mathrm{\mid }$ in $\mathrm{\mid }x\mathrm{\mid }$, one can construct in time polynomial in $\mathrm{\mid }x\mathrm{\mid }$ formulas $F_{\mathrm{\exists }}(x;y,z)$ in 3CNF and $F_{\mathrm{\forall }}(x;y,z)$ in 3DNF such that, for every allowed $y$, $R(x,y)⟺\mathrm{\exists }z{F}_{\mathrm{\exists }}(x;y,z)⟺\mathrm{\forall }z{F}_{\mathrm{\forall }}(x;y,z)\mathrm{.}$ Here clauses or terms have at most three literals. Both formula length and $\mathrm{\mid }z\mathrm{\mid }$ are polynomially bounded. (Ph circuit matrix final block encoding).

Let $A\subseteq {\mathrm{\Sigma }}^{\ast }$ and $B\subseteq {\mathrm{\Gamma }}^{\ast }$ be languages over finite alphabets. A polynomial-time many-one reduction from $A$ to $B$ is a total function $f:{\mathrm{\Sigma }}^{\ast }\to {\mathrm{\Gamma }}^{\ast }$ such that: - $f$ is computable by a deterministic Turing machine in polynomial time, and - for every $x\in {\mathrm{\Sigma }}^{\ast }$, $x\in A⟺f(x)\in B\mathrm{.}$ When such an $f$ exists, write $A{\le }_{p}B\mathrm{.}$ (Polynomial-time many-one reductions).