Course contentsShow
← Computer Science
Lesson 1909 of 2,87243. Complexity TheoryFree lesson

Complementary Classes: coNP

Define coNP as problems whose complements are in NP and examine relationships between P, NP, and coNP.

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.