If X is in NP then $\overline{X}$ is in NP.

True, false or "we don't know"? Why?

  • $\begingroup$ We don't know whether NP=coNP. $\endgroup$ – Yuval Filmus Jul 9 at 20:21
  • $\begingroup$ @YuvalFilmus why? $\endgroup$ – user784343 Jul 9 at 20:23
  • 1
    $\begingroup$ I'm not sure how to answer this. People have tried but failed to show either NP=coNP or NP≠coNP. $\endgroup$ – Yuval Filmus Jul 9 at 20:24
  • $\begingroup$ @user784343 are you asking why we don't know...? $\endgroup$ – Steven Jul 9 at 20:24
  • $\begingroup$ @Steven exactly $\endgroup$ – user784343 Jul 9 at 20:25

The answer is unknown. If $X\in NP$ and $\bar X\in \mathcal{NP}$ than by definition it's a so called "co-NP" problem ($X\in \mathcal{coNP}$). It's still an open problem if $\mathcal{NP} = \mathcal{coNP}$.

An example:
Some problems are known to be in coNP. E.g. to decide if two number $n,m$ have a common divisor $>1$. This problem is in $\mathcal{NP}$ because there exists a polynomial verifier to check if a "proof" that some $n,m$ have common divisor $>1$ exists. The verifier accepts e.g. a number $p$ if $p>1$ and $p|n \land p|m$ the verifier accepts the proof. Now lets show that the complement of this language is also in $\mathcal{NP}$. We need to construct a verifier that accepts a proof that two numbers don't have a common divisor $>1$. You might notice that this is a bit more difficult but it can be done. The verifier accepts the prime factorization of $n$ and $m$ and checks that these are really the prime factorization of $n$ and $m$ and then that they don't have a common element.

Now try SAT...
Now if you take e.g. the $SAT$ problem and you try to find a verifier for $\overline{SAT}$ you have to find an algorithm that can given a certain proof verify that a boolean expression does not have a solution in polynomial time. If you think about it this is quite tricky (some how you have to deduce from the proof that none of the exponentially many variable assignments is valid) and it's currently not known whether $SAT\in \mathcal{coNP}$.

| cite | improve this answer | |

Your Answer

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

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