12
$\begingroup$

How to prove that $\mathsf{NP}^A \neq \mathsf{coNP}^A$ ? I am just looking for a such oracle TM $M$ and a recursive language $L(M) = L$ for which this holds.

I know the proof where you show that there is an oracle $A$ such that $\mathsf{P}^A \neq \mathsf{NP}^A$ and an oracle $A$ such that $\mathsf{P}^A = \mathsf{NP}^A$. I have a hint that I should find such oracle $A$ by extending the proof of $\mathsf{P}^A \neq \mathsf{NP}^A$ but wherever I search and read, it is "obvious" or "straightforward" everywhere but I just do not see how prove it at all.

$\endgroup$
  • 6
    $\begingroup$ It's not clear whether you've followed up on the hint. I am surprised to hear that $P^A \neq NP^A$ is obvious, but you can find the proof in (for example) Computational Complexity: A Modern Approach by Arora and Barak. $\endgroup$ – Max May 14 '12 at 11:41
9
$\begingroup$

As Max said the modification is not difficult, I suggest that you do not read the rest of this answer and think about the problem a little bit more, there is only one part that needs modification and remembering the definition of when a $\mathsf{coNP}$ machine accepts will help you fix that part.

I will explain the required modification below, but first let's have a brief view at the original proof.

In the original proof $A=\bigcup_n A_n$ is built in steps where at step $i$ with make sure that $i$th machine in $\mathsf{P}$, $M_i$, doesn't decide the language $\{x \mid \exists y\in A \ |x|=|y| \}$ correctly. Note that the set is in $\mathsf{NP}^A$.

We achieve this by simulating $M_i$ using the part of $A$ we have built on a $0^m$ where $m$ is large enough (the string is longer than strings considered in previous steps). $M_i$ accepts, we don't add anything, if it rejects we add a string of length $m$ that $M_i$ doesn't make a query to the set (Such a string exists since there are exponentially many strings of length $m$ but $M_i$ cannot ask about all of them in polynomial time). We will not modify this part of $A$ in future steps (i.e. strings of length $m$ or less will stay the same). This makes sure that $M_i^A$ will not decide the language correctly and completes the proof.

Now, assume that the machines $M_i$ were in $\mathsf{coNP}$ in place of $\mathsf{P}$. We need to modify the proof to make sure that $M_i^A$ will not recognize $L$. If it is accepting we keep $A$ as before and everything works fine as in the original proof. If it rejects, we need to add a string to the set to make sure it doesn't answer correctly. We still can simulate $M_i$ with the part of $A$ we have, the problem is that $M_i$ might query all strings of length $n$. Here the way a $\mathsf{coNP}$ machine works becomes important. It accepts if and only if all computation paths accept. Since it is rejecting in this case, there is a computation path that is rejecting. As long as we keep this path intact everything will work, so we only need to keep the answers to the queries in that path the same. The number of queries in this path is polynomial (since the machine runs in polynomial time), so there are strings of length $m$ that the path doesn't query about, just add one of them to $A$ and the rest of the proof works as before.

The steps are algorithmic, so the set $A$ is recursive (the essential part of the construction is being able to simulate machines which can be done in say $\mathsf{DSpace}(n^{\omega(1)})$).

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

You may also wish to consult the text Computational Complexity by Christos Papadimitriou. Specifically Chapter 14, Section 3 that delves into oracles. Proofs for $P^A = NP^A$ and $P^B \not= NP^B$ for some oracles $A$ and $B$ for instance are provided in detail, and may be helpful for your primary problem. Hope that helps.

| cite | improve this answer | |
$\endgroup$

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.