What is the difference between NP and coNP?

Question

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?

Answer 1

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.