Polynomial hierarchy: inclusion between spaces

Question

Using the definition for the polynomial hierarchy:

$$ \Sigma_{i+1}^P = NP^{\Sigma_i^P} $$ $$ \Pi_{i+1}^P = coNP^{\Sigma_i^P} $$

I have been asked to to show that:

$$ P^{\Pi_k^P } \subseteq \Pi_{k+1}^P $$

I don't really have many ideas on how to go for it:

by definition $ P^{\Pi_k^P } $ is the set of languages accepted by a $PTIME$ deterministic TM with an oracle answering queries in $\Pi_k^P$, while $\Pi_{k+1}^P$ is the set of languages accepted by a universal alternating TM, with an oracle answering queries in $\Sigma_k^P$.
If I could use a universal ATM $M_A$ to simulate a DTM (and I would say I can't) then I should be able to recognize a language $L \in P^{\Pi_k^P}$ by noticing that $L$ is accepted by a DTM $M$ that uses the oracle $O$ (that answers about $\Pi_k^P$), thus taking a universal ATM $M_A$ to simulate $M$ and another universal ATM $M_O$ (accepting queries in $\Pi_{k+1}^P$) to simulate the oracle (since $\Pi_k^P \subseteq \Pi_{k+1}^P $).

But I really think this reasoning cannot be done, as actually I'm not using the oracle…how should I approach the problem?

Answer 1

Using the definition of Papadimitrou for polynomial hierarchy, or for that matter from wiki, the proof is really simple. $\Delta^P_{k+1} = P^{\Pi_k^P} \subseteq CoNP^{\Pi_k^P} = CoNP^{\Sigma_k^P} = \Pi^P_{k+1}$. Similarly $\Delta^P_{k+1} \subseteq \Sigma^P_{k+1}$.

But if the definition of polynomial hierarchy is done by alternating quantifiers than also we can prove it in the following way. The proof follows the book "Computational Complexity" by Arora and Barak, yet you have to flip a few $\exists$ and $\forall$, and do some negations. Assume equal fixed polynomial length certificates in the following proof.

We know that $P^{\Pi_k^P} = P^{\Pi_k^{SAT}} = P^{\Sigma_k^{SAT}}$.

Suppose that $L$ is decidable by a polynomial-time DTM $M$ with oracle access to $\Sigma_k^{SAT}$. Then, $x$ is in $L$ if and only if there exists a sequence of oracle answers that makes $M$ accept $x$. That is, if $a_1 , . . . , a_m \in \{0, 1\}$ is a sequence of (correct) answers to oracle queries on input $x$, that is, the machine $M$ receives $a_i$ as the answer to its $i$ th query, then (1) $M$ reaches the accepting state $q_{accept}$ and (2) all the answers are correct. $m$ is the maximum number of oracle queries.

We can modify DTM $M$ so that it will make exactly $m$ queries for the given input size $|x|=n$, i.e $m$ is not varying depending on the outcomes of the oracle. $m$ will be (less than) a polynomial in $n$. $m$ can also be made polynomial time computable by possibly taking a larger value. The proof is made further difficult because there are polynomial number of queries and each $i$-th query may be different depending on the answers of previous queries. Also we need to convert $\exists a_1, a_2,...$ to $\forall a_1,a_2,...$ is the proof by Arora and Barak.

Let $\phi_{i,a_1,a_2,...,a_{i-1}}$ denote the $i$-th query that $M$ makes to its oracle when executing on $x$ receiving answers $a_1 , . . . , a_{i-1}$ . $\phi_{i,a_1,a_2,...,a_{i-1}}$ can be generated by a turing machine (which is similar to $M$ in some ways) in polynomial time. Then, the condition (2) can be phrased as follows:

if $a_i = 1$ then $ \exists u_1 \forall u_2 ... \phi_{i,a_1,a_2,...,a_{i-1}}(u_1,u_2,...,u_k ) = 1$ and if $a_i = 0$ then $ \forall v_1 \exists v_2 ... \phi_{i,a_1,a_2,...,a_{i-1}} (v_1,v_2,...,v_k ) = 0$.

Now we have the following:

$x \in L$
iff $\forall a_1 , . . . , a_m \in \{0,1\}$
$\exists i \in [1..m]$ if $a_i = 1$ then $\forall U_i^1 \exists U_i^2, \forall U_i^3,...\phi_{i,a_1,a_2,...,a_{i-1}}(U_i^1, U_i^2,U_i^3,...,U_i^k) = 0$
OR $\exists i \in [1..m]$ if $a_i = 0$ then $\exists V_i^1\forall V_i^2, \exists V_i^3,...\phi_{i,a_1,a_2,...,a_{i-1}} (V_i^1,V_i^2,V_i^3,...,V_i^k) = 1$
OR $M$ accepts $x$ using answers $a_1 , . . . , a_k$

This implies that $L \in \Pi_{k+1}^P$ since $\phi_{i,a_1,a_2,...,a_{i-1}} \in \Sigma_k^{SAT}$. ( You can club all quantifiers as $\forall a_1 , . . . , a_k , U^1_1 , U^1_2 . . , U^1_m \exists V^1_1 , . . . , V^1_m, U^2_1, U^2_2, ... U^2_m \forall V^2_2,..., V^2_m, U^3_1, ...U^3_m \exists ...$ , the certificates are still polynomial).

We can actually prove $NP^{\Sigma^P_k} = \Sigma^P_{k+1}$ and $CoNP^{\Pi^P_k} = \Pi^P_{k+1}$ using similar methods if I remember correctly.

The inclusion graph is given pictorially below,