Is $\sf{P^{NP \cap coNP}} = \sf{NP \cap coNP}$?

First, this result is listed in the complexity zoo: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#npiconp. Alternatively, it's possible to prove without much trouble (which I do below).

We want to show that $P^{NP \cap coNP} = NP \cap coNP$. Clearly, one direction is obviously true: $NP \cap coNP \subseteq P^{NP \cap coNP}$. To prove the other direction, it is sufficient to show that $P^{NP \cap coNP} \subseteq NP$ since then $P^{NP \cap coNP} \subseteq coNP$ follows simply by complementing all the languages involved and as a result $P^{NP \cap coNP} \subseteq NP \cap coNP$.

So let's prove that $P^{NP \cap coNP} \subseteq NP$.

Suppose we have a deterministic polynomial time machine $M$ which makes oracle queries for languages in $NP \cap coNP$. We define a new, non-deterministic machine $M'$ based on $M$ as follows:

Simulate $M$ until $M$ needs to run an oracle query on some input $x$ for some language $L$. At that point, run a subroutine which branches $M'$ into some number of branches each of which attempts to learn the answer to the oracle query. The subroutine is designed so that no branch learns the wrong answer, at least one branch learns the correct answer, and some branches get "inconclusive" as a result when trying to learn the answer to the query. In $M'$, the branches with inconclusive results then reject. At this point, the only branches left are ones which know the correct answer to the query. Thus we can continue the simulation of $M$ in these branches. At the end of the simulation, the only branches which haven't rejected are the ones which successfully got through all of the steps of the simulation. These branches accept iff $M$ accepts, so the overall $NP$

Since $L \in NP \cap coNP$, there exists a NP machine $N_L$ with language $L$ and another machine $N_{\neg L}$ whose language is the complement of $L$. To simulate the oracle query (is $x$ in $L$), $M'$ first runs $N_L$ on $x$ and then runs $N_{\neg L}$ on $x$ in every branch. Every resulting branch will have one branch of $N_L$'s computation and one branch of $N_{\neg L}$'s computation. Within any single branch, both the $N_L$ computaion and the $N_{\neg L}$ computation cannot be accepting since that would require $x$ to both be in $L$ and in $\neg L$. Thus each branch will have either the $N_L$ computation accepting, the $N_{\neg L}$ computation accepting, or neither computation accepting. Furthermore, there must be at least one accepting branch of either $N_L$ or $N_{\neg L}$. Next, $M'$ rejects in the branches in which the computations of both $N_L$ and $N_{\neg L}$ reject. In all other branches, $M'$ has learned the answer to the oracle query (since either $N_L$ or $N_{\neg L}$ accept $x$ in the particular branch considered in this $M'$ branch). At that point, $M'$ can continue the simulation of $M$. Note that the simulation will actually continue in at least one branch since at least one accepting branch of either $N_L$ or $N_{\neg L}$ exits.

Solved by user34401 (2,718 )
Mar 18, 2017 at 02:31