co-NP

NP is the class of yes/no problems where a YES answer has a short, easily-checkable certificate: a jigsaw that is hard to finish but easy to verify once someone hands you the finished picture. co-NP is its mirror image: it is the class where a NO answer has a short, easily-checkable certificate. If NP is about producing a convincing witness that the answer is yes, co-NP is about producing a convincing witness that the answer is no. They are two sides of the same verification coin.

Formally, a problem is in co-NP exactly when its complement (swap every yes and no) is in NP. The poster child is TAUTOLOGY: is this boolean formula true under every assignment? A single failing assignment would prove it is NOT a tautology, so the complement (non-tautology, a fancy SAT) is in NP, putting TAUTOLOGY in co-NP. Equivalently, co-NP problems are those verifiable by a 'for all' check: 'yes' means every candidate passes, which is hard to confirm by example but easy to refute with one counterexample. Note P is contained in both NP and co-NP, because a deterministic polynomial algorithm settles yes and no symmetrically.

co-NP matters as the natural partner of NP and the first rung of the polynomial hierarchy above it. The great open question here is whether NP equals co-NP. Almost everyone believes NOT: it seems far harder to certify that a formula has NO satisfying assignment than to exhibit one that works. If NP did equal co-NP it would be a seismic result, and it would NOT by itself settle P versus NP, though P not equal to NP would follow if NP not equal to co-NP. Caveat against a tempting confusion: co-NP is not 'the problems NOT in NP'. Many problems sit in BOTH NP and co-NP (everything in P does, and famously integer factoring's decision version does too), and whether the two classes are equal is unknown.