I believe $\mathrm{co}(\mathrm{NP}^A) = (\mathrm{coNP})^A$:

By definition, $L \in (\mathrm{coNP})^A$ means there is a PTIME Turing machine $M$, allowed to make oracle calls to $A$, such that for any word $w$, all computations of $M$ when started with $w$ on its input tape end in "reject" iff $w \in L$.

In other words, for any word $w$, there is some computation of $M$ (with oracle calls to $A$) that ends in "accept" iff $w \notin L$, i.e., iff $\overline{L} \in \mathrm{NP}^A$ iff $L \in \mathrm{co}(\mathrm{NP}^A)$.

Is this right?

  • 5
    $\begingroup$ This question seems obvious and not research level to me. I would ask if I was missing something subtle, but the question is very clearly written, so I don't think I am... Voting to close. $\endgroup$ Mar 22, 2013 at 15:53
  • $\begingroup$ I think the official definition for $coNP$ is complement of $NP$. So they are equal by definition. It also seems to me that it is easy to prove that it is equivalent to languages of polytime conondeterministic TMs by the standard method of switching accepting and rejecting states. The computation tree will be the same, and every accepting path becomes a rejecting one and vice versa. So if all paths were rejecting in the NTM machine, all of them become accepting in the coNTM machine. Having oracles doesn't seem to play a role. $\endgroup$
    – Kaveh
    Mar 22, 2013 at 15:53
  • $\begingroup$ I'm not sure I'd want to say that coNP is the "complement" of NP, since then I'd need to overload "complement" to handle collection of sets, also leading to confusion because for example $A \subset B \implies \overline{B} \subset \overline{A}$ but $C \subset C' \implies co-C \subset co-C'$ $\endgroup$ Mar 22, 2013 at 19:01
  • $\begingroup$ @Suresh, I agree it might be confusing for unfamiliar people but that is the terminology used on Complexity Zoo. $\endgroup$
    – Kaveh
    Mar 22, 2013 at 19:30
  • 1
    $\begingroup$ Where is the question? Seems like the definition of the LHS and RHS are the same. $\endgroup$
    – domotorp
    Mar 23, 2013 at 6:14


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.