The class NP favours positive answers: if the answer is yes, there is a short, checkable proof. But many natural questions have the opposite shape. "Is this formula true for every assignment?", "Does this graph have no clique of size k?", "Does this circuit behave correctly on all inputs?". Questions of this kind need a mirror class: coNP.
The definition
coNP = {L : the complement of L belongs to NP}
In terms of certificates: a language is in coNP if its negative answers have short certificates checkable in polynomial time. Equivalently, w ∈ L if and only if for every string c of polynomial length some polynomial verifier accepts ⟨w, c⟩.
The comparison with NP can be summed up like this:
| Class | Shape of the condition | Short certificate for |
|---|---|---|
| NP | there exists c such that V(w, c) | yes |
| coNP | for every c, V(w, c) holds | no |
Mind the name: coNP is not the complement of the class NP, that is it does not contain "all problems not in NP". It contains the complements of the individual problems in NP.
The canonical problem: tautologies
A Boolean formula is a tautology if it is true under every assignment of its variables.
TAUT = {⟨φ⟩ : φ is a tautology}
TAUT is in coNP: if φ is not a tautology, the certificate is an assignment making it false, and checking it is immediate. Note the link with SAT:
φ is a tautology if and only if ¬φ is unsatisfiable.
It follows that TAUT is coNP-complete: every problem in coNP reduces in polynomial time to TAUT, just as every problem in NP reduces to SAT. In general, if A is NP-complete, its complement is coNP-complete.
Other examples of coNP-complete problems:
- unsatisfiability: the formula has no satisfying assignment;
- non-Hamiltonicity: the graph has no cycle passing through every node once;
- circuit equivalence: two Boolean circuits compute the same function on every input.
The last one is a real problem in hardware verification: proving that an optimized circuit is equivalent to the original.
NP versus coNP
We know that P ⊆ NP ∩ coNP, because P is closed under complement: if you can settle yes in polynomial time, you can settle no as well. But we do not know whether NP = coNP.
Some certain facts:
- if P = NP, then NP = coNP, because P = coP;
- if an NP-complete problem belonged to coNP, then NP = coNP;
- so, if NP ≠ coNP were proved, P ≠ NP would follow.
The widespread conjecture is NP ≠ coNP. Concretely, it would mean there are no short certificates for unsatisfiability: no way to convince someone quickly that a formula has no solutions, at least in the worst case. This ties the question to proof complexity: a proof system for tautologies in which every tautology has a proof of polynomial length exists if and only if NP = coNP.
The borderland: NP ∩ coNP
Problems in NP ∩ coNP have short certificates for both yes and no. They are considered unlikely to be NP-complete, because that would imply NP = coNP.
Interesting examples:
- primality: it was known to lie in NP ∩ coNP (a divisor certifies that a number is composite, and Pratt certificates certify that it is prime) long before it was proved to be in P;
- factoring in the decision version "does N have a prime factor smaller than k?": the certificate, for both yes and no, is the full factorization of N, checkable in polynomial time thanks to the primality test;
- linear programming, whose decision version has certificates of feasibility and, thanks to duality theory, certificates of infeasibility; here too membership in P was later proved.
The history of primality and linear programming suggests that lying in NP ∩ coNP is a good hint of an efficient algorithm still to be found. For factoring, though, nobody has found one on classical computers.
A glance at the polynomial hierarchy
NP corresponds to one existential quantifier, coNP to one universal quantifier. They can be alternated:
- Σ₂ᵖ: there exists c₁ such that for every c₂, V(w, c₁, c₂) holds;
- Π₂ᵖ: for every c₁ there exists c₂ such that V(w, c₁, c₂) holds;
- and so on, with more and more alternations.
An example of a problem in Σ₂ᵖ: "is there a formula with at most k symbols equivalent to the given formula?". We must find the small formula (there exists) and check that it is equivalent under every assignment (for every).
The union of all these levels is called the polynomial hierarchy (PH), and it is contained in PSPACE. All levels are conjectured to be distinct; if two consecutive levels coincided, the whole hierarchy would collapse to that level.
In short
- coNP contains the problems whose negative answers have short certificates.
- TAUT is coNP-complete, because φ is a tautology if and only if ¬φ is unsatisfiable.
- P ⊆ NP ∩ coNP; NP ≠ coNP is conjectured, and it would imply P ≠ NP.
- Primality, decision factoring and linear programming lie in NP ∩ coNP.
- Alternating existential and universal quantifiers yields the polynomial hierarchy.
