What is the difference between NP and coNP? Is coNP a subset of NP ? or vice versa? What is the significance of NP $\cap$ coNP when it comes to mathematics?
$\endgroup$ 62 Answers
$\begingroup$NP is the class of decision problems for which there is a polynomial time algorithm that can verify "yes" instances given the appropriate certificate.
CoNP is the class of decision problems for which there is a polynomial time algorithm that can verify "no" instances given the appropriate certificate.
We don’t know whether coNP is different from NP.
There is a problem in NP for every problem in coNP, and vice versa. For example, the SAT problem asks "does there exist a boolean assignment which makes this formula evaluate to True?". The complement problem, which is in coNP, asks, "do all boolean assignments make this formula evaluate to False?"
$\endgroup$ $\begingroup$There are several definitions that all end up equivalent. However, my favorite has to do with verification. $NP$ is the class of problems where it's easy (read "takes polynomial time, if given help") to verify that there is a solution. For example, it's easy to convince someone that a SAT instance is solvable, just give them a satisfying assignment and they can check if all the clauses are satisfied.
Likewise, $CO-NP$ problems are easy to show that there isn't a solution. For example, checking if a Boolean function is unchanged when we switch the first two inputs. I only need to show you one case where $f(x,y,\cdots) \neq f(y,x,\ldots)$ to show that it's not symmetric, however it's not at all clear how to show if this function is symmetric.
Because we can't easily show a SAT instance is unsatisfiable, nor that a function is symmetric, neither $NP$ nor $CO-NP$ is known to be a subset of the other.
Being in both means that you can easily check either way, given a proof (like a satisfying assignment or a counterexample). Examples include every problem we can solve in polynomial time, which require no help to verify, the curious can quickly run a poly time algorithm themselves to verify an answer.
$\endgroup$
