[proofplan] Membership is obtained by interpreting the quantified Boolean blocks as the alternating polynomial-size certificates in the definitions of $\Sigma_k^P$ and $\Pi_k^P$, with the quantifier-free Boolean matrix evaluated deterministically in polynomial time. For hardness, we start from the verifier characterization of a language in $\Sigma_k^P$ or $\Pi_k^P$, choose a deterministic polynomial-time verifier for the final predicate, and encode that verifier's computation by a polynomial-size local tableau formula. The only point requiring care is the final quantified block: existential final blocks assert the existence of a valid accepting tableau, while universal final blocks use an implication so that invalid tableaus do not create false constraints. This preserves the number of quantifier blocks and yields a polynomial-time many-one reduction. [/proofplan] [step:Show that bounded quantified satisfiability lies in the corresponding polynomial hierarchy level] Fix $k \geq 1$. Let $\Phi$ be an input to $\mathrm{QSAT}_k^\exists$, written as \begin{align*} \Phi = \exists Y_1\, \forall Y_2\, \exists Y_3\, \cdots\, Q_k Y_k\, \varphi(Y_1,\dots,Y_k), \end{align*} where each $Y_i$ is a finite block of Boolean variables and $\varphi$ is a quantifier-free Boolean formula. Define the deterministic predicate $E_\varphi: \{0,1\}^{|Y_1|} \times \cdots \times \{0,1\}^{|Y_k|} \to \{0,1\}$ by declaring $E_\varphi(a_1,\dots,a_k)=1$ exactly when the assignment $Y_i=a_i$ for all $i$ makes $\varphi$ true. The predicate $E_\varphi$ is decidable in time polynomial in $|\Phi|$, because evaluating a Boolean formula on a complete assignment takes time polynomial in the formula length. Therefore truth of $\Phi$ has the form of a $\Sigma_k^P$ computation with $k$ alternating polynomial-size Boolean certificates. Now let $\Psi$ be an input to $\mathrm{QSAT}_k^\forall$, written as \begin{align*} \Psi = \forall Y_1\, \exists Y_2\, \forall Y_3\, \cdots\, Q_k'Y_k\, \psi(Y_1,\dots,Y_k), \end{align*} where each $Y_i$ is a finite block of Boolean variables and $\psi$ is a quantifier-free Boolean formula. Define the deterministic predicate $E_\psi: \{0,1\}^{|Y_1|} \times \cdots \times \{0,1\}^{|Y_k|} \to \{0,1\}$ by declaring $E_\psi(a_1,\dots,a_k)=1$ exactly when the assignment $Y_i=a_i$ for all $i$ makes $\psi$ true. The predicate $E_\psi$ is decidable in time polynomial in $|\Psi|$, because evaluating a Boolean formula on a complete assignment takes time polynomial in the formula length. Therefore truth of $\Psi$ has the form of a $\Pi_k^P$ computation with $k$ alternating polynomial-size Boolean certificates and a deterministic polynomial-time final predicate. Hence $\mathrm{QSAT}_k^\exists \in \Sigma_k^P$ and $\mathrm{QSAT}_k^\forall \in \Pi_k^P$. [/step] [step:Encode a $\Sigma_k^P$ verifier by a bounded quantified Boolean formula] Let $L \in \Sigma_k^P$. We use the verifier characterization of $\Sigma_k^P$: for languages over $\{0,1\}^*$, membership is expressible by $k$ alternating certificate blocks, each of length bounded by a single polynomial in the input length, followed by a deterministic predicate decidable in polynomial time on the combined input. Therefore there exist a polynomial $p:\mathbb{N}\to\mathbb{N}$ and a deterministic polynomial-time predicate $R: \{0,1\}^* \times \{0,1\}^* \times \cdots \times \{0,1\}^* \to \{0,1\}$ with $k+1$ inputs such that, for every $x \in \{0,1\}^*$, \begin{align*} x \in L \iff \exists y_1 \in \{0,1\}^{p(|x|)}\, \forall y_2 \in \{0,1\}^{p(|x|)}\, \cdots\, Q_k y_k \in \{0,1\}^{p(|x|)}\, R(x,y_1,\dots,y_k)=1. \end{align*} Choose a deterministic Turing machine $M$ deciding $R$ in time $t(n)$, where $t:\mathbb{N}\to\mathbb{N}$ is a polynomial and $n$ denotes the total input length. For each fixed $x$, introduce Boolean variable blocks $Y_1,\dots,Y_k$ encoding $y_1,\dots,y_k$, each of length $p(|x|)$. Also introduce a Boolean block $Z$ whose assignments encode complete computation tableaus of $M$ on input $(x,Y_1,\dots,Y_k)$ for $t((k+1)p(|x|)+|x|)$ time steps. By the standard local-tableau encoding for deterministic polynomial-time Turing-machine computations, applied to the fixed deterministic machine $M$ and the time bound $t((k+1)p(|x|)+|x|)$, the tableau has polynomial size in $|x|$ because $t$ and $p$ are polynomials, and the local consistency constraints are constructible in time polynomial in $|x|$. Thus there are quantifier-free Boolean formulas \begin{align*} H_x(Y_1,\dots,Y_k,Z) \end{align*} and \begin{align*} A_x(Z) \end{align*} such that, for every tuple $(y_1,\dots,y_k)$ and every tableau encoding $z$, the formula $H_x(y_1,\dots,y_k,z)$ is true exactly when $z$ is the valid computation history of $M$ on input $(x,y_1,\dots,y_k)$, and $A_x(z)$ is true exactly when the final configuration encoded in $z$ is accepting. Since $M$ is deterministic, for every fixed tuple $(x,y_1,\dots,y_k)$ there is exactly one valid tableau $z^*(x,y_1,\dots,y_k)$, and \begin{align*} R(x,y_1,\dots,y_k)=1 \iff H_x(y_1,\dots,y_k,z^*) \wedge A_x(z^*). \end{align*} If $Q_k=\exists$, define the quantified Boolean formula \begin{align*} \Phi_x = \exists Y_1\, \forall Y_2\, \cdots\, \exists (Y_k,Z)\, \bigl(H_x(Y_1,\dots,Y_k,Z) \wedge A_x(Z)\bigr). \end{align*} For each fixed tuple $(y_1,\dots,y_k)$, the final existential quantifier over $Z$ is true exactly when there exists a valid accepting computation history of $M$ on that input, which is equivalent to $R(x,y_1,\dots,y_k)=1$. If $Q_k=\forall$, define \begin{align*} \Phi_x = \exists Y_1\, \forall Y_2\, \cdots\, \forall (Y_k,Z)\, \bigl(\neg H_x(Y_1,\dots,Y_k,Z) \vee A_x(Z)\bigr). \end{align*} For each fixed tuple $(y_1,\dots,y_k)$, the final universal quantifier over $Z$ asserts that every tableau is either invalid or accepting. All invalid tableaus satisfy the implication automatically, and the unique valid tableau is among the universally quantified assignments. Thus the final universal condition is true exactly when the unique valid computation history is accepting, again equivalent to $R(x,y_1,\dots,y_k)=1$. [guided] The reduction must encode the polynomial-time predicate $R$ without adding an extra alternation. Let us make the construction explicit. Since $L \in \Sigma_k^P$, the verifier characterization supplies exactly the data needed for a bounded quantified formula: a polynomial certificate-length bound $p:\mathbb{N}\to\mathbb{N}$ and a deterministic predicate $R$ decidable in polynomial time on the combined input. Thus membership in $L$ is witnessed by alternating Boolean strings: \begin{align*} x \in L \iff \exists y_1 \in \{0,1\}^{p(|x|)}\, \forall y_2 \in \{0,1\}^{p(|x|)}\, \cdots\, Q_k y_k \in \{0,1\}^{p(|x|)}\, R(x,y_1,\dots,y_k)=1. \end{align*} The hypotheses are used here as follows: every quantified certificate block has polynomial length $p(|x|)$, the number of alternations is exactly $k$, and the remaining predicate is deterministic polynomial time. Choose a deterministic Turing machine $M$ deciding $R$ in polynomial time. The quantified Boolean formula we build will use blocks $Y_i$ to represent the certificate strings $y_i$. The remaining problem is to replace the assertion "$M$ accepts $(x,y_1,\dots,y_k)$" by a quantifier-free Boolean formula. Introduce a tableau block $Z$. An assignment to $Z$ is intended to encode a complete computation history of $M$ on input $(x,Y_1,\dots,Y_k)$. The local-tableau construction for deterministic polynomial-time computations, applied to this fixed machine $M$ and to its polynomial time bound on inputs of the form $(x,Y_1,\dots,Y_k)$, gives quantifier-free formulas $H_x(Y_1,\dots,Y_k,Z)$ and $A_x(Z)$ in time polynomial in $|x|$. The formula $H_x$ checks that $Z$ is a valid initial-to-final computation history of $M$ on the encoded input, using local consistency constraints between consecutive configurations. The formula $A_x$ checks that the final configuration encoded by $Z$ is accepting. The deterministic nature of $M$ is essential. For every fixed tuple $(x,y_1,\dots,y_k)$, there is exactly one valid computation history $z^*(x,y_1,\dots,y_k)$. Hence the truth of $R(x,y_1,\dots,y_k)$ is equivalent to acceptance of that one tableau: \begin{align*} R(x,y_1,\dots,y_k)=1 \iff H_x(y_1,\dots,y_k,z^*) \wedge A_x(z^*). \end{align*} Now consider the parity of the last quantifier. If the last block is existential, we may enlarge it from $Y_k$ to $(Y_k,Z)$ and use the matrix \begin{align*} H_x(Y_1,\dots,Y_k,Z) \wedge A_x(Z). \end{align*} For fixed earlier variables, this says that there exists a tableau $Z$ that is both valid and accepting. Since there is exactly one valid tableau, this is equivalent to saying that $M$ accepts. If the last block is universal, we cannot use the matrix $H_x \wedge A_x$, because that would demand that every possible tableau string be a valid accepting computation history. Most arbitrary strings are not valid histories, so that formula would be false for the wrong reason. The correct universal encoding is the implication \begin{align*} H_x(Y_1,\dots,Y_k,Z) \implies A_x(Z), \end{align*} written as the quantifier-free Boolean formula \begin{align*} \neg H_x(Y_1,\dots,Y_k,Z) \vee A_x(Z). \end{align*} Invalid tableaus satisfy this formula automatically. The unique valid tableau is included among the universally quantified assignments to $Z$, so the universal statement holds exactly when that unique valid tableau is accepting. Thus the tableau variables can be placed inside the final universal block without creating a new quantifier block. In both parity cases, substituting the tableau formula for the predicate $R(x,y_1,\dots,y_k)=1$ preserves the original $k$ alternating quantifier blocks and preserves the leading existential quantifier. The construction of $H_x$ and $A_x$ is polynomial-time computable in $|x|$, and the added tableau variables are placed only inside the final block. Therefore the map $x \mapsto \Phi_x$ is a polynomial-time many-one reduction satisfying \begin{align*} x \in L \iff \Phi_x \in \mathrm{QSAT}_k^\exists. \end{align*} [/guided] In both cases the map $x \mapsto \Phi_x$ is computable in time polynomial in $|x|$, the formula $\Phi_x$ has exactly $k$ alternating quantifier blocks, begins with an existential block, and satisfies \begin{align*} x \in L \iff \Phi_x \in \mathrm{QSAT}_k^\exists. \end{align*} Therefore every language in $\Sigma_k^P$ many-one reduces to $\mathrm{QSAT}_k^\exists$, so $\mathrm{QSAT}_k^\exists$ is $\Sigma_k^P$-hard. [/step] [step:Reverse the leading quantifier to obtain $\Pi_k^P$ hardness] Let $L \in \Pi_k^P$. We use the verifier characterization of $\Pi_k^P$: for languages over $\{0,1\}^*$, membership is expressible by $k$ alternating certificate blocks, beginning with a universal block, each of length bounded by a single polynomial in the input length, followed by a deterministic predicate decidable in polynomial time on the combined input. Hence there exist a polynomial $p:\mathbb{N}\to\mathbb{N}$ and a deterministic polynomial-time predicate $R: \{0,1\}^* \times \{0,1\}^* \times \cdots \times \{0,1\}^* \to \{0,1\}$ such that, for every $x \in \{0,1\}^*$, \begin{align*} x \in L \iff \forall y_1 \in \{0,1\}^{p(|x|)}\, \exists y_2 \in \{0,1\}^{p(|x|)}\, \cdots\, Q_k' y_k \in \{0,1\}^{p(|x|)}\, R(x,y_1,\dots,y_k)=1. \end{align*} Choose a deterministic Turing machine $M$ deciding $R$ in polynomial time, and apply the standard local-tableau encoding for deterministic polynomial-time computations to $M$. Introduce a tableau block $Z$ whose assignments encode complete computations of $M$ on input $(x,Y_1,\dots,Y_k)$ for the polynomial time bound used by $M$. Because the certificate blocks have polynomial length and $M$ runs in polynomial time, the tableau has polynomial size in $|x|$ and the local constraints are constructible in polynomial time. Obtain quantifier-free formulas $H_x(Y_1,\dots,Y_k,Z)$ and $A_x(Z)$ such that $H_x$ holds exactly for valid computation histories and $A_x$ holds exactly for accepting final configurations. If $Q_k'=\exists$, enlarge the final existential block to $(Y_k,Z)$ and use matrix \begin{align*} H_x(Y_1,\dots,Y_k,Z) \wedge A_x(Z). \end{align*} For each fixed tuple $(y_1,\dots,y_k)$, determinism of $M$ gives a unique valid tableau $z^*(x,y_1,\dots,y_k)$. Therefore the final existential condition over $Z$ holds exactly when this unique valid tableau is accepting, which is equivalent to $R(x,y_1,\dots,y_k)=1$. If $Q_k'=\forall$, enlarge the final universal block to $(Y_k,Z)$ and use matrix \begin{align*} \neg H_x(Y_1,\dots,Y_k,Z) \vee A_x(Z). \end{align*} For each fixed tuple $(y_1,\dots,y_k)$, every invalid tableau satisfies the displayed disjunction because $\neg H_x$ holds. The unique valid tableau $z^*(x,y_1,\dots,y_k)$ is included among the universally quantified assignments, and for that assignment the disjunction reduces to $A_x(z^*)$. Hence the final universal condition is true exactly when the unique valid computation history is accepting, which is equivalent to $R(x,y_1,\dots,y_k)=1$. Substituting this exact equivalent of $R(x,y_1,\dots,y_k)=1$ into the verifier expression for $L \in \Pi_k^P$ gives \begin{align*} x \in L \iff \Psi_x \in \mathrm{QSAT}_k^\forall. \end{align*} The transformation $x \mapsto \Psi_x$ is polynomial-time computable and preserves the $k$ alternating quantifier blocks with leading universal quantifier. Hence $\mathrm{QSAT}_k^\forall$ is $\Pi_k^P$-hard. [/step] [step:Combine membership and hardness] From the first step, $\mathrm{QSAT}_k^\exists \in \Sigma_k^P$ and $\mathrm{QSAT}_k^\forall \in \Pi_k^P$. From the second and third steps, $\mathrm{QSAT}_k^\exists$ is $\Sigma_k^P$-hard and $\mathrm{QSAT}_k^\forall$ is $\Pi_k^P$-hard under polynomial-time many-one reductions. Therefore $\mathrm{QSAT}_k^\exists$ is $\Sigma_k^P$-complete and $\mathrm{QSAT}_k^\forall$ is $\Pi_k^P$-complete for every integer $k \geq 1$. [/step]