7
$\begingroup$

If it is unknown, are there reasons to believe that they might not be equal?

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thanks! I actually checked the complexity zoo but somehow missed the "Equals $\sf{P^{NP \cap coNP}}$" statement. I have only one question. Why would your proof fail to show $\sf{P^{NP}} = NP$? I'm always hesitant when designing a non-deterministic algorithm/Turing machine to do anything else after the non-deterministic branching to not fall in the trap of giving a $\sf{P^{NP}}$ algorithm instead of an $\sf{NP}$ one. In your proof if the oracle were just an $\sf{NP}$ oracle, then couldn't M' simulate it the same way as you described here (only run $N_L$ in the simulation) ? Where's the catch? $\endgroup$ – user1033363 Mar 18 '17 at 9:32
  • $\begingroup$ (just to add a clarification, $\sf{P^{NP}}$ contains $\sf{coNP}$ since the $\sf{P}$ machine can just negate the answers of the $\sf{NP}$ oracle. So if $\sf{P^{NP}} = \sf{NP}$ then $\sf{NP} = \sf{coNP}$ and the polynomial hierarchy would collapse) $\endgroup$ – user1033363 Mar 18 '17 at 9:45
  • 4
    $\begingroup$ In my proof, I rely on the existence of both an NP machine and a coNP machine for the language of the oracle in order foor the simulation to branch such that each branch either gets a result of "inconclusive" or the correct answer. If all you have for the language of the oracle is an NP machine, then you are not guaranteed that some branch gets a conclusive answer: in the case that the NP machine rejects, every branch rejects, which is inconclusive. Thus the same proof fails to show $P^{NP} \subseteq NP$. More generally, an $NP$ oracle is more powerful than an $NP \cap coNP$ oracle. $\endgroup$ – Mikhail Rudoy Mar 18 '17 at 21:21

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.