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?

  • $\begingroup$ How do you define $\mathit{NP}^{\Sigma^p_k \cap \Pi^p_k}$? $\endgroup$ – Yuval Filmus Mar 30 '14 at 4:00
  • $\begingroup$ 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? $\endgroup$ – bellpeace Mar 30 '14 at 4:11
  • $\begingroup$ One problem or many problems? In my answer, I assume that you get to choose one language. $\endgroup$ – 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$.

  • $\begingroup$ 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. $\endgroup$ – bellpeace Mar 30 '14 at 19:27
  • $\begingroup$ The difference would be that you would need machines $P_{\pm}$ for the infinitely many languages in $\Sigma^p_k \cap \Pi^p_k$. $\endgroup$ – Yuval Filmus Mar 30 '14 at 19:40
  • $\begingroup$ Ok, sure. But in what sense would that change invalidate the above proof? $\endgroup$ – bellpeace Mar 30 '14 at 19:53
  • $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Mar 30 '14 at 20:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.