If X is in NP then $\overline{X}$ is in NP.
True, false or "we don't know"? Why?
$\begingroup$
$\endgroup$
8
-
$\begingroup$ We don't know whether NP=coNP. $\endgroup$– Yuval FilmusCommented Jul 9, 2020 at 20:21
-
$\begingroup$ @YuvalFilmus why? $\endgroup$– user784343Commented Jul 9, 2020 at 20:23
-
2$\begingroup$ I'm not sure how to answer this. People have tried but failed to show either NP=coNP or NP≠coNP. $\endgroup$– Yuval FilmusCommented Jul 9, 2020 at 20:24
-
$\begingroup$ @user784343 are you asking why we don't know...? $\endgroup$– StevenCommented Jul 9, 2020 at 20:24
-
$\begingroup$ @Steven exactly $\endgroup$– user784343Commented Jul 9, 2020 at 20:25
|
Show 3 more comments
2 Answers
$\begingroup$
$\endgroup$
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}$.
$\begingroup$
$\endgroup$
To give you an idea of the “why”: A yes/no problem is an NP if you can prove the answer is “yes” by making an incredibly lucky guess, plus some moderate amount of work.
For example: Can I make a tour connecting the capitals of the 48 main states of the USA in at most 10,000 miles? If the answer is “yes” then I make a lucky guess in which order to visit the 48 capitals, and then just add up the distances. But if the answer is “no” then no such guessing will work. If I guess one order that takes 10,100 miles, that doesn’t prove there isn’t a better order.
The questions look very similar, but checking that an x exists is easy if you can guess x; checking that no x exists often cannot be helped by guessing. Or at least we haven’t figured out a way yes.
