[proofplan] We prove the identities directly from the alternating-quantifier definition of the polynomial hierarchy. Complementation swaps existential and universal quantifier blocks and negates the final polynomial-time predicate, giving the duality $\Pi_k^P = co\Sigma_k^P$. The first containment is immediate because a deterministic polynomial-time machine with a $\Sigma_k^P$ oracle can make one query to decide a $\Sigma_k^P$ language. For the second containment, we encode a polynomial-time oracle computation by its full query transcript and verify the transcript with one additional alternation, placing $P^{\Sigma_k^P}$ inside both $\Sigma_{k+1}^P$ and $\Pi_{k+1}^P$. Finally, the oracle characterisations follow by separating the leading nondeterministic choice from the remaining $k-1$ alternations, and then taking complements. [/proofplan] [step:Complement alternating quantifiers to identify $\Pi_k^P$ with $co\Sigma_k^P$] Fix an integer $k \geq 1$. Let $L \subseteq \{0,1\}^*$ be a language in $\Sigma_k^P$. By the alternating-quantifier definition, there exist a polynomial $p:\mathbb{N}\to\mathbb{N}$, a polynomial-time decidable predicate \begin{align*} R:\{0,1\}^* \times (\{0,1\}^*)^k \to \{0,1\}, \end{align*} and quantifiers $Q_1,\dots,Q_k$, with $Q_1=\exists$ and alternating thereafter, such that for every input $x \in \{0,1\}^*$, \begin{align*} x \in L \iff Q_1 y_1 \in \{0,1\}^{p(|x|)} \, Q_2 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*} Taking complements gives \begin{align*} x \notin L \iff \overline{Q}_1 y_1 \in \{0,1\}^{p(|x|)} \, \overline{Q}_2 y_2 \in \{0,1\}^{p(|x|)} \cdots \overline{Q}_k y_k \in \{0,1\}^{p(|x|)} \, R'(x,y_1,\dots,y_k)=1, \end{align*} where $\overline{\exists}=\forall$, $\overline{\forall}=\exists$, and \begin{align*} R':\{0,1\}^* \times (\{0,1\}^*)^k \to \{0,1\} \end{align*} is the polynomial-time predicate defined by \begin{align*} R'(x,y_1,\dots,y_k)=1 \iff R(x,y_1,\dots,y_k)=0. \end{align*} The quantifier string now begins with $\forall$ and alternates, so $\overline{L}\in \Pi_k^P$. Hence $co\Sigma_k^P \subseteq \Pi_k^P$. The same argument with the roles of $\exists$ and $\forall$ reversed shows that if $L \in \Pi_k^P$, then $\overline{L}\in \Sigma_k^P$, so $L \in co\Sigma_k^P$. Therefore \begin{align*} \Pi_k^P = co\Sigma_k^P. \end{align*} [guided] Fix $k \geq 1$. The definition of $\Sigma_k^P$ says that membership in a language is decided by a polynomial-time predicate after $k$ alternating blocks of polynomially bounded guesses, beginning with an existential block. Thus, for $L \in \Sigma_k^P$, there are a polynomial $p:\mathbb{N}\to\mathbb{N}$ and a polynomial-time predicate \begin{align*} R:\{0,1\}^* \times (\{0,1\}^*)^k \to \{0,1\} \end{align*} such that \begin{align*} x \in L \iff Q_1 y_1 \in \{0,1\}^{p(|x|)} \, Q_2 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*} where $Q_1=\exists$ and the quantifiers alternate. To describe the complement language $\overline{L}$, we negate the right-hand side. Negating an existential statement produces a universal statement, negating a universal statement produces an existential statement, and the final predicate is replaced by its Boolean complement. Define \begin{align*} R':\{0,1\}^* \times (\{0,1\}^*)^k \to \{0,1\} \end{align*} by \begin{align*} R'(x,y_1,\dots,y_k)=1 \iff R(x,y_1,\dots,y_k)=0. \end{align*} Since $R$ is decidable in polynomial time, $R'$ is also decidable in polynomial time by running the algorithm for $R$ and flipping its answer. Therefore \begin{align*} x \in \overline{L} \iff \overline{Q}_1 y_1 \in \{0,1\}^{p(|x|)} \, \overline{Q}_2 y_2 \in \{0,1\}^{p(|x|)} \cdots \overline{Q}_k y_k \in \{0,1\}^{p(|x|)} \, R'(x,y_1,\dots,y_k)=1. \end{align*} The new quantifier string begins with $\forall$ and alternates, which is precisely the defining pattern for $\Pi_k^P$. Hence $\overline{L}\in \Pi_k^P$, proving $co\Sigma_k^P \subseteq \Pi_k^P$. The reverse inclusion is obtained by applying the same complementation argument to a $\Pi_k^P$ definition: a string beginning with $\forall$ becomes one beginning with $\exists$, and the final polynomial-time predicate remains polynomial-time after negation. Thus every $\Pi_k^P$ language is the complement of a $\Sigma_k^P$ language. Consequently \begin{align*} \Pi_k^P = co\Sigma_k^P. \end{align*} [/guided] [/step] [step:Simulate a $\Sigma_k^P$ language by one deterministic oracle query] Let $L \in \Sigma_k^P$. A deterministic polynomial-time oracle machine with oracle $L$ decides $L$ by querying its oracle once on the input $x$ and accepting exactly when the oracle answers yes. Since $L$ itself is a valid $\Sigma_k^P$ oracle, this gives $L \in P^{\Sigma_k^P}=\Delta_{k+1}^P$. Therefore \begin{align*} \Sigma_k^P \subseteq \Delta_{k+1}^P. \end{align*} [/step] [step:Encode deterministic $\Sigma_k^P$ oracle computations inside $\Sigma_{k+1}^P$] Let $L \in \Delta_{k+1}^P=P^{\Sigma_k^P}$. Then there exist a language $A \in \Sigma_k^P$ and a deterministic polynomial-time oracle machine $M^A$ deciding $L$. Let $m:\mathbb{N}\to\mathbb{N}$ be a polynomial bounding the running time of $M^A$ and the lengths of all oracle queries on inputs of length $n$. Since $A \in \Sigma_k^P$, there are a polynomial $p:\mathbb{N}\to\mathbb{N}$, a polynomial-time predicate \begin{align*} R:\{0,1\}^* \times (\{0,1\}^*)^k \to \{0,1\}, \end{align*} and alternating quantifiers $Q_1,\dots,Q_k$, with $Q_1=\exists$, such that for every query string $q \in \{0,1\}^*$, \begin{align*} q \in A \iff Q_1 z_1 \in \{0,1\}^{p(|q|)} \, Q_2 z_2 \in \{0,1\}^{p(|q|)} \cdots Q_k z_k \in \{0,1\}^{p(|q|)} \, R(q,z_1,\dots,z_k)=1. \end{align*} For an input $x$, an accepting computation of $M^A$ is described by a finite transcript $T$ containing every query $q_j$ made by $M$ and the proposed oracle answer $a_j \in \{0,1\}$, for $1 \leq j \leq r$, where $r \leq m(|x|)$. The transcript is locally checkable in polynomial time: simulating $M$ using the listed answers determines whether the queries are exactly the listed queries and whether the simulated final state accepts. A proposed transcript is correct exactly when every listed answer agrees with $A$. For positive answers $a_j=1$, correctness requires $q_j \in A$, a $\Sigma_k^P$ condition. For negative answers $a_j=0$, correctness requires $q_j \notin A$, a $\Pi_k^P$ condition. A polynomially long conjunction of such conditions can be written with one additional leading existential block by existentially guessing the transcript and the existential witnesses for all positive oracle answers, while the remaining alternating blocks verify both the positive and negative oracle claims in parallel. Hence the set of inputs admitting an accepting correct transcript has a $\Sigma_{k+1}^P$ definition. Therefore $L \in \Sigma_{k+1}^P$, and hence \begin{align*} \Delta_{k+1}^P \subseteq \Sigma_{k+1}^P. \end{align*} [guided] Let $L \in \Delta_{k+1}^P$. By definition, this means $L$ is decided by a deterministic polynomial-time oracle machine $M^A$ for some oracle language $A \in \Sigma_k^P$. We fix a polynomial $m:\mathbb{N}\to\mathbb{N}$ that bounds the running time of $M^A$ and the length of every query produced by $M$ on inputs of length $n$. Because $A \in \Sigma_k^P$, there are a polynomial $p:\mathbb{N}\to\mathbb{N}$ and a polynomial-time predicate \begin{align*} R:\{0,1\}^* \times (\{0,1\}^*)^k \to \{0,1\} \end{align*} such that \begin{align*} q \in A \iff \exists z_1 \in \{0,1\}^{p(|q|)} \, \forall z_2 \in \{0,1\}^{p(|q|)} \cdots Q_k z_k \in \{0,1\}^{p(|q|)} \, R(q,z_1,\dots,z_k)=1. \end{align*} The displayed formula starts with an existential block and has $k$ alternating blocks. Now fix an input $x$. Since $M$ is deterministic once the oracle answers are supplied, an entire oracle computation can be recorded by a transcript $T$. This transcript lists the queries \begin{align*} q_1,\dots,q_r \in \{0,1\}^{\leq m(|x|)} \end{align*} and proposed answers \begin{align*} a_1,\dots,a_r \in \{0,1\}, \end{align*} where $r \leq m(|x|)$. A polynomial-time verifier can simulate $M$ on $x$ using these proposed answers and check that the listed queries are exactly the queries produced by the simulation and that the resulting final state is accepting. The only nontrivial issue is verifying that the proposed oracle answers are correct. If $a_j=1$, we must verify $q_j \in A$, which is a $\Sigma_k^P$ statement. If $a_j=0$, we must verify $q_j \notin A$, which is a $\Pi_k^P$ statement by the duality already proved. Since there are only polynomially many queries, we can combine all these checks into one alternating formula: the outermost existential block guesses the transcript $T$ and the first existential witnesses required for all positive oracle answers. The subsequent universal and existential blocks range over the corresponding witness strings for all queries in parallel. The final polynomial-time predicate checks the local validity of the transcript, all positive oracle-answer certificates, and all negative oracle-answer refutations. This construction adds only one leading existential block in front of the $k$ oracle-definition blocks. Thus membership in $L$ is expressible by a $\Sigma_{k+1}^P$ formula. Therefore \begin{align*} L \in \Sigma_{k+1}^P. \end{align*} Since $L \in \Delta_{k+1}^P$ was arbitrary, we obtain \begin{align*} \Delta_{k+1}^P \subseteq \Sigma_{k+1}^P. \end{align*} [/guided] [/step] [step:Complement the oracle computation to obtain the $\Pi_{k+1}^P$ containment] Let $L \in \Delta_{k+1}^P$. Since deterministic polynomial-time oracle computation is closed under complement by swapping accepting and rejecting final states, the complement language $\overline{L}$ also lies in $\Delta_{k+1}^P$. By the previous step, \begin{align*} \overline{L} \in \Sigma_{k+1}^P. \end{align*} Using $\Pi_{k+1}^P=co\Sigma_{k+1}^P$, this implies \begin{align*} L \in \Pi_{k+1}^P. \end{align*} Together with $L \in \Sigma_{k+1}^P$, we have \begin{align*} L \in \Sigma_{k+1}^P \cap \Pi_{k+1}^P. \end{align*} Thus \begin{align*} \Delta_{k+1}^P \subseteq \Sigma_{k+1}^P \cap \Pi_{k+1}^P. \end{align*} [/step] [step:Separate the leading existential block to obtain $\Sigma_k^P = NP^{\Sigma_{k-1}^P}$] Fix an integer $k \geq 2$. First let $L \in \Sigma_k^P$. Then there exist a polynomial $p:\mathbb{N}\to\mathbb{N}$ and a polynomial-time predicate \begin{align*} R:\{0,1\}^* \times (\{0,1\}^*)^k \to \{0,1\} \end{align*} such that \begin{align*} x \in L \iff \exists y_1 \in \{0,1\}^{p(|x|)} \, \Phi(x,y_1), \end{align*} where $\Phi(x,y_1)$ is the remaining $(k-1)$-alternation condition \begin{align*} \forall y_2 \in \{0,1\}^{p(|x|)} \, \exists y_3 \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 predicate $\Phi$ is a $\Pi_{k-1}^P$ condition, and by the already proved duality $\Pi_{k-1}^P=co\Sigma_{k-1}^P$. An $NP$ machine with a $\Sigma_{k-1}^P$ oracle guesses $y_1$ and decides $\Phi(x,y_1)$ by querying the complement of the corresponding $\Sigma_{k-1}^P$ language, equivalently by flipping the answer to the $\Sigma_{k-1}^P$ oracle query. Hence \begin{align*} L \in NP^{\Sigma_{k-1}^P}. \end{align*} Conversely, let $L \in NP^{\Sigma_{k-1}^P}$. Let $N^A$ be a nondeterministic polynomial-time oracle machine deciding $L$, where $A \in \Sigma_{k-1}^P$. A branch of $N^A$ is determined by a polynomially bounded nondeterministic string and a polynomially bounded oracle-answer transcript. As in the deterministic transcript argument, correctness of all oracle answers can be verified with the $(k-1)$ alternating blocks defining $A$, and the nondeterministic choices of $N$ supply the leading existential block. Therefore membership in $L$ is expressible by a $\Sigma_k^P$ formula. Hence \begin{align*} NP^{\Sigma_{k-1}^P} \subseteq \Sigma_k^P. \end{align*} Combining the two inclusions gives \begin{align*} \Sigma_k^P = NP^{\Sigma_{k-1}^P}. \end{align*} [/step] [step:Take complements to obtain $\Pi_k^P = coNP^{\Sigma_{k-1}^P}$] For $k \geq 2$, the equality just proved gives \begin{align*} co\Sigma_k^P = coNP^{\Sigma_{k-1}^P}. \end{align*} Using the duality $\Pi_k^P=co\Sigma_k^P$, we conclude \begin{align*} \Pi_k^P = coNP^{\Sigma_{k-1}^P}. \end{align*} This completes the proof of all stated containments and dualities. [/step]