Problems that are Cook-reducible to a problem in NP $\cap$ co-NP

Question

Let $\mathcal{A}$ be a problem in $\text{NP} \cap \text{co}$-$\text{NP}$.

Now assume we can reduce another problem $\mathcal{B}$ to it using Cook reduction.

What conclusions can we draw about $\mathcal{B}$? Does this question even make sense?

I'm asking because from what I understand Cook reductions differ from Karp reductions (for example, $\text{NP}$ cannot be distinguished from $\text{co}$-$\text{NP}$). I'm pretty confused and can't seem to really understand the properties of Cook reductions. Any good reference about the topic would also be appreciated!

I hope this question is not too basic, but I was not able to find anything about it.

Answer 1

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}\cap\mathsf{coNP}$? Is $\mathsf{NP}\cap\mathsf{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}\cap\mathsf{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 $A\in \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 $A\in\mathsf{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 $A\in\mathsf{NP\cap coNP}$, that is why this does not work for $A \in\mathsf{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 $1\leq 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 $Q\in\mathsf{coNP}$. So $Q\in\mathsf{NP\cap coNP}$. In other words, $\mathsf{P^{NP\cap coNP}} \subseteq \mathsf{NP\cap coNP}$.

Answer 2

If $\mathcal{A} \in \mathrm{NP} \cap \mathrm{co\text{-}NP}$, then there is a witness for $x \in \mathcal{A}$ as well as for $x \notin \mathcal{A}$. In other words, if I give you a computation with oracle to access to $\mathcal{A}$, I can convince that I didn't lie about the oracle answers by giving the appropriate witnesses.

Since $\mathcal{B}$ Cook-reduces to $\mathcal{A}$, you can solve $\mathcal{B}$ in polynomial time using an oracle to $\mathcal{A}$. Connecting the dots, we conclude that $\mathcal{B} \in \mathrm{NP} \cap \mathrm{co\text{-}NP}$.