Complementary Classes: coNP
What you'll learn: You'll discover what coNP is and how it relates to P and NP by flipping the "yes/no" question around.
The Core Idea
In complexity theory, coNP is the class of decision problems whose complements are in NP.
Think of it this way: if a problem asks "Does this graph have a Hamiltonian cycle?" (an NP problem), the complement asks "Does this graph lack a Hamiltonian cycle?"
For NP problems, when the answer is "yes," there's a short, easily verifiable certificate (proof). For coNP problems, when the answer is "no," there's a short, easily verifiable certificate.
The Complement Relationship
A language L is in coNP if its complement (the set of all strings not in L) is in NP.
Example: TAUTOLOGY (determining if a Boolean formula is always true) is in coNP. Why? Because its complement, "Is this formula not a tautology?" (meaning it has at least one false assignment), is in NP—you can verify it with a satisfying assignment that makes the formula false.
Relationships Between P, NP, and coNP
Here's what we know:
- P ⊆ NP: Every polynomial-time problem is in NP
- P ⊆ coNP: Every polynomial-time problem is also in coNP (if you can decide it efficiently, you can decide its complement efficiently)
- P = coP: P is closed under complementation
The big question: Is NP = coNP? We don't know! Most researchers believe NP ≠ coNP, but it's unproven. If P = NP, then automatically NP = coNP = P.
Key Takeaway: coNP contains problems whose "no" answers have short, verifiable proofs; it's the mirror image of NP, and whether NP = coNP remains one of complexity theory's open questions.