[Solved]: Problems that are Cook-reducible to a problem in NP $cap$ co-NP

Nice question/homework! Stated in another way: $mathsf{NP}$ is not closed under Cook reductions (assuming $mathsf{P}neq mathsf{NP}$). How about $mathsf{NP}capmathsf{coNP}$? Is $mathsf{NP}capmathsf{coNP}$ closed under Cook reductions? Is the only reason that $mathsf{NP}$ is not closed under Cook reductions is because it is not closed under complement so if we take those $mathsf{NP}$ problems whose complement is also $mathsf{NP}$ do we get around the problem? For example, if we have a Cook reduction from a problem to Factoring, would that mean that the problem is in $mathsf{NP}capmathsf{coNP}$? An oracle doesn’t just allow us to ask about membership and non-membership in the oracle, it allows us to ask very complicated list of questions where each question can depend on the answer for the previous one. Let’s look at a problem $Q in mathsf{P^{NP cap coNP}}$. We know that there is a polynomial-time algorithm $M$ and a set $Ain mathsf{NP cap coNP}$ such that $M^A$ solves the problem $Q$. Is $Q$ in $mathsf{NP}$? Hint: when does $M^A$ accept an input $x$? Don’t read the answer below if this is an assignment, the answer is not difficult, you should be able to solve it if you spend a few hours on it, and spending those hours is what makes you learn.

Let’s look at the execution of $M^A$ on an input $x$. $M$ will make a number of queries to $A$ during its computation and will receive YES and NO answers, and finally will accept or reject. If we could compute that answers to the queries in polynomial time we would have shown that the problem is in $mathsf{P}$, we would simulate the algorithm $M$ and whenever it asked a query from $A$ we would compute the answer and give to $M$ and continue with its simulation.

But $Ainmathsf{NP cap coNP}$ and we don’t know how to compute the answers to queries in polynomial time. But we don’t need to do this in polynomial-time! We can just guess the answers to the questions and verify our guesses in polynomial-time. To be able to verify the answers for both positive and negative answers we need $Ainmathsf{NPcap coNP}$, that is why this does not work for $A inmathsf{NP}$, that would allow only verifying positive answers.

Let $V_{YES}$ and $V^{NO}$ be two polynomial-time verifiers for membership and non-membership in $A$. Consider the verfier $V(x,y)$ which works as follows:

I. check that $y$ consists of 1. a string $c$ (computation of $M$ on $x$), 2. a list of strings $q_1,ldots,q_m$ (queries to the oracle in $c$), 3. a list of strings $a_1,ldots,q_m$ (answers to queries from oracle), 4. a list of strings $w_1,ldots,w_m$ (certificates/proofs/witnesses for the correctness of the query answers).
II. check that the list of queries $q_1,ldots,q_m$ contains all oracle queries in $c$,
III. check that the computation $c$ is an accepting computation of $M$ on $x$ if answers to the queries are $a_1,ldots,a_m$.
IV. for all $1leq i leq m$, check that if $a_i=YES$ then $V^{YES}$ accepts $(q_i,w_i)$ and if $a_i=NO$ then $V^{NO}$ accepts $(q_i,w_i)$.

All of these steps can be checked in polynomial-time. So we have a verifier for YES answers of $M^A$. Furthermore note that if $M^A$ accepts $x$, then there is $y$ satisfying these conditions which has polynomial-size: the computation of a polynomial-time machine is of polynomial-size and the number of queries and the size of all queries are also polynomial in the input. Moreover the size of certificates for queries are also bounded by some polynomial in the size of the queries, so again are polynomial in the size of input. In short we have a polynomial-time verifier with polynomial-size certificates for $M^A$.
This completes the proof that $Q in mathsf{NP}$. A similar argument shows that $Qinmathsf{coNP}$. So $Qinmathsf{NPcap coNP}$. In other words, $mathsf{P^{NPcap coNP}} subseteq mathsf{NPcap coNP}$.