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$ – Joshua Grochow Mar 22 '13 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 '13 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$ – Suresh Venkat Mar 22 '13 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 '13 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 '13 at 6:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.