# (Why) is $NP\subseteq coNP/poly$ same as $coNP\subseteq NP/poly$?

If I rememeber right, I read somewhere that $$NP\subseteq coNP/poly$$ is the same as $$coNP\subseteq NP/poly$$. Is this true? If yes, is there a relatively simple proof for this?

## Definitions

Class $$NP/poly$$.
We say that a language $$L$$ belongs to the complexity class $$NP/poly$$ if there is a Turing machine $$M$$ and a sequence of strings $$\{a_n\colon n\in\mathbb{N}\}$$ called advice, such that the following hold.

• Machine $$M$$, when given an input $$x$$ of length $$n$$, has access to the string $$a_n$$ and has to decide whether $$x\in L$$. Machine $$M$$ works in nondeterministic polynomial time.
• $$|a_n|\leq p(n)$$ for some polynomial $$p$$.

$$coNP/poly$$ is the complement of $$NP/poly$$.

Is the following definition correct?

Class $$coNP/poly$$.
We say that a language $$L$$ belongs to the complexity class $$coNP/poly$$ if there is a Turing machine $$M$$ and a sequence of strings $$\{a_n\colon n\in\mathbb{N}\}$$ called advice, such that such that the following hold.

• Machine $$M$$, when given an input $$x$$ of length $$n$$, has access to the string $$a_n$$ and has to decide whether $$x\notin L$$. Machine $$M$$ works in nondeterministic polynomial time.
• $$|a_n|\leq p(n)$$ for some polynomial $$p$$.

## 1 Answer

By definition, $$L \in \mathsf{coNP} \Longleftrightarrow \overline{L} \in \mathsf{NP} \\ L \in \mathsf{coNP/poly} \Longleftrightarrow \overline{L} \in \mathsf{NP/poly}$$ From this you can easily deduce your claim.