1
$\begingroup$

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$.
$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.