# Polynomial hierarchy intersection

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?

• How do you define $\mathit{NP}^{\Sigma^p_k \cap \Pi^p_k}$? – Yuval Filmus Mar 30 '14 at 4:00
• As languages for which there is an NTM with an oracle for problems in $\Sigma_{k}^{p} \cap \Pi_{k}^{p}$. Is that what you were looking for? – bellpeace Mar 30 '14 at 4:11
• One problem or many problems? In my answer, I assume that you get to choose one language. – Yuval Filmus Mar 30 '14 at 4:16

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$.

• What would be the difference if we could query the oracle for any problem in $\Sigma_{k}^{p} \cap \Pi_{k}^{p}$? It seems that conceptually there should be no difference. – bellpeace Mar 30 '14 at 19:27
• The difference would be that you would need machines $P_{\pm}$ for the infinitely many languages in $\Sigma^p_k \cap \Pi^p_k$. – Yuval Filmus Mar 30 '14 at 19:40
• Ok, sure. But in what sense would that change invalidate the above proof? – bellpeace Mar 30 '14 at 19:53
• It depends how you present the questions to the oracle. If the language is described through the machines $P_{\pm}$ then the proof should go through. Otherwise, you might need to "know" the machines $P_{\pm}$ corresponding to all languages in $\Sigma^p_k \cap \Pi^p_k$. – Yuval Filmus Mar 30 '14 at 20:04