Polynomial hierarchy intersection

Question

While familiarizing myself with polynomial hierarchy, I have come across a problem of showing $NP^{\Sigma_{k}^{p} \cap \Pi_{k}^{p}} \subseteq \Sigma_{k}^{p}$. By looking at the proof for $NP^{SAT} \subseteq \Sigma_{2}^{p}$, I got the concept where we can guess the choices of the NTM and answers to SAT call and then encode the correctness of these answers. However, while I understand encoding correctness of answers for SAT calls, I have a problem of doing the same for the oracle $\Sigma_{k}^{p} \cap \Pi_{k}^{p}$, which has no known complete problems. It seems to me there is a cookbook way of proving this that I am missing?

Answer 1

I will assume the following definition for $\mathit{NP}^{\Sigma_k^p \cap \Pi_k^p}$: it is the class of languages decided by polytime non-deterministic Turing machines with oracle access to a language in $\Sigma_k^p \cap \Pi_k^p$. Consider now some $L \in \mathit{NP}^{\Sigma_k^p \cap \Pi_k^p}$ which is decided by some NP machine $M$ with oracle access to a language $K \in \Sigma_k^p \cap \Pi_k^p$.

Since $K \in \Sigma_k^p \cap \Pi_k^p$, there are $\Sigma_k^p$-witnesses to both $x \in K$ and $x \notin K$. Including all such witnesses, the NP machine $M$ becomes an absolute $\Sigma_k^p$ machine (we fold the first $\exists$ quantifier).

In more detail, we can write $L$ as $x \in L \leftrightarrow \exists |y|<|x|^C P(x,y)$ for some predicate $P$ which is polynomial time with oracle access to $K$. Since $P$ runs in polynomial time, it makes at most polynomially many queries to $O$. We construct a new predicate $P'$ which guesses the results $b_1,\ldots,b_T$ of these queries $q_1,\ldots,q_T$. Since $K \in \Sigma_k^p \cap \Pi_k^p$, if $b_i = T$ ($b_i = F$) then for some polytime $P_+$ ($P_-$) we have $$\exists |w_{i,1}| < |x|^{C_1} \forall |w_{i,2}| < |x|^{C_2} \cdots Q |w_{i,k}| < |x|^{C_k} P_{\pm}(q_i,w_{i,1},\ldots,w_{i,k}).$$ By combining $P$ with the machines $P_+,P_-$ we can come up with a polytime predicate $P'$ such that $$ x \in L \leftrightarrow \exists |y| < |x|^C \exists b_1,\ldots,b_T \exists |w_{1,1}|,\ldots,|w_{T,1}| < |x|^{C_1} \cdots Q |w_{1,k}|,\ldots,|w_{T,k}| < |x|^{C_k} \\ P'(x,y,\vec{b},\vec{w}). $$ Folding the first three existential quantifiers, we see that $L \in \Sigma^p_k$.