co-NP and the P-versus-NP question
/ co-NP = koh-en-pee /
NP has a built-in lopsidedness: it promises a short, checkable proof for YES answers, but says nothing about NO answers. co-NP is the mirror image — the class of problems whose NO answers have short, checkable proofs. If SAT ('is this formula satisfiable?') is in NP because a satisfying assignment witnesses 'yes', then its complement UNSAT ('is this formula unsatisfiable?') is in co-NP: a 'no' for UNSAT (i.e. it IS satisfiable) is witnessed by an assignment, but a 'yes' (truly unsatisfiable) seems to have no short certificate at all. Whether such proofs of unsatisfiability must always be long is one of the great open questions.
Precisely, a problem is in co-NP if its COMPLEMENT (swap yes and no) is in NP. Equivalently, co-NP problems have a polynomial-time verifier for NO-instances: every 'no' comes with a short certificate that the verifier checks. P sits inside BOTH NP and co-NP, because if you can SOLVE a problem in polynomial time you can certify either answer (just re-run the algorithm), so the answer needs no separate proof. The famous P-versus-NP question asks whether P = NP: is every problem whose yes-answers are quickly CHECKABLE also quickly SOLVABLE? Equivalently, can the lucky guessing of nondeterminism always be replaced by honest deterministic work at only polynomial extra cost? A proof either way would be monumental: P = NP would mean SAT, protein folding, and thousands of optimisation problems all become tractable (and most modern cryptography would break); P not equal NP would confirm the intuition that some problems are intrinsically search-hard. It is one of the seven Millennium Prize Problems, with a million-dollar bounty, and despite decades of effort it remains wide open.
Three honest clarifications. First, almost everyone CONJECTURES P is not NP, but it is a belief, not a theorem — every claim built on it (including 'NP-complete means no efficient algorithm') carries that caveat. Second, there is a related conjecture that NP is not equal to co-NP; if they were equal, unsatisfiability would have short proofs, which experts doubt. If NP = co-NP fails, then P not equal NP follows, but not vice versa, so these are layered open problems. Third, a subtle structural fact (Ladner's theorem): IF P is not NP, then NP is not cleanly split into just 'easy P' and 'hardest NP-complete' — there must also exist NP-INTERMEDIATE problems, in NP but neither in P nor NP-complete. So the landscape, assuming the conjecture, is richer than a two-way split, with candidates like factoring and graph isomorphism suspected to live in that middle ground.
Tautology checking is the classic co-NP problem: 'is this boolean formula true under EVERY assignment?'. A 'no' has a short certificate — one assignment that makes it false, checkable instantly. But a 'yes' (it really is a tautology) seems to need you to rule out all 2^n assignments, with no obvious short proof. That asymmetry is exactly why TAUTOLOGY is in co-NP and conjectured not to be in NP.
co-NP: NO-answers have short proofs. P is inside NP and co-NP; P=?NP and NP=?co-NP stay open.
P not equal NP is a CONJECTURE, not a proven fact — 'NP-complete' formally means 'no polynomial algorithm unless P = NP'. Also NP and co-NP are conjectured distinct; if they were equal, unsatisfiability would have short proofs, which would be a shock.