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

<p>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$. </p>

<p>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)$.</p>

<p>Is this right?</p>

CC BY-SA 3.0
2013-03-22T15:53:19.833Z
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.
Joshua Grochow
CC BY-SA 3.0
2013-03-22T15:53:23.093Z
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.
Kaveh
CC BY-SA 3.0
2013-03-22T19:01:58.823Z
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'$
Suresh Venkat
CC BY-SA 3.0
2013-03-22T19:30:19.587Z
@Suresh, I agree it might be confusing for unfamiliar people but that is the terminology used on [Complexity Zoo](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:C#conp).
Kaveh
CC BY-SA 3.0
2013-03-23T06:14:48.727Z
Where is the question? Seems like the definition of the LHS and RHS are the same.
domotorp
<cc.complexity-theory>
Is $\mathrm{co}(\mathrm{NP}^A) = (\mathrm{coNP})^A$?
Joel
# Is $\mathrm{co}(\mathrm{NP}^A) = (\mathrm{coNP})^A$?

(Asked by: username_0 on 2013-03-22)

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?

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_3**: 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'$  
> **username_2**: @Suresh, I agree it might be confusing for unfamiliar people but that is the terminology used on [Complexity Zoo](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:C#conp).  
> **username_4**: Where is the question? Seems like the definition of the LHS and RHS are the same.  

---

## 0 answers

