Co-NP-complete
In computational complexity theory, a decision problem is co-NP-complete when it belongs to co-NP and every problem in co-NP can be transformed into it by a polynomial-time reduction. Such problems therefore occupy within co-NP the position occupied by NP-complete problems within NP. The definition is usually stated with respect to polynomial-time many-one reductions, although other reduction notions produce related completeness classes.
The prefix “co” denotes complementation rather than cooperation or simultaneous nondeterministic computation. A language belongs to co-NP precisely when its complement belongs to NP. Consequently, a language is co-NP-complete exactly when its complement is NP-complete, provided that the same many-one reduction convention is used for both classifications.
Definition
Let (L) be a language over a finite alphabet. The language (L) is co-NP-complete under polynomial-time many-one reductions when both of the following conditions hold:
- (L) belongs to co-NP, meaning that its complement (\overline{L}) belongs to NP.
- For every language (A) in co-NP, there is a polynomial-time computable function (f) satisfying [ x \in A \iff f(x) \in L. ]
The second condition expresses co-NP-hardness. Membership and hardness are logically distinct: a co-NP-hard language need not itself belong to co-NP, while a language in co-NP need not represent the full reduction-theoretic difficulty of the class.
Complementation preserves the relevant reduction structure. If (A) reduces to (L) through (f), then (\overline{A}) reduces to (\overline{L}) through the same function, because [ x \in \overline{A} \iff f(x) \in \overline{L}. ] It follows directly that (L) is co-NP-complete if and only if (\overline{L}) is NP-complete.
Certificate interpretation
The class NP admits a characterization through polynomially bounded certificates that can be verified in polynomial time. For a language in co-NP, the corresponding certificates establish nonmembership rather than membership. If (L) belongs to co-NP, every input outside (L) has a polynomial-size certificate accepted by an appropriate polynomial-time verifier.
This asymmetry is visible in logical decision problems. A propositional formula that is not a tautology has a compact witness consisting of an assignment under which the formula evaluates to false. A tautology, by contrast, asserts that no falsifying assignment exists. The straightforward certificate mechanism therefore applies to the complement of the tautology problem.
The certificate characterization does not establish that members of a co-NP language lack concise affirmative proofs under every proof formalism. It states only that co-NP is defined through polynomial verification of negative instances. Whether every co-NP language also has polynomially verifiable certificates for its positive instances is equivalent to the question of whether NP equals co-NP.
Canonical complete problems
The standard co-NP-complete problem is TAUT, whose instances are propositional formulas and whose positive instances evaluate to true under every Boolean assignment. Its complement consists of formulas having at least one falsifying assignment. Since that complementary problem is NP-complete, TAUT is co-NP-complete.
The Boolean satisfiability problem asks whether a formula has at least one satisfying assignment. Its complement, UNSAT, asks whether no satisfying assignment exists and is co-NP-complete. The completeness of UNSAT follows immediately from the NP-completeness of satisfiability and the complement duality between NP and co-NP.
Equivalent examples arise by complementing other NP-complete languages. For instance, deciding that a graph has no Hamiltonian cycle is co-NP-complete because the existence of such a cycle is NP-complete. These complementary formulations preserve the mathematical content of the original decision problems while exchanging existential acceptance conditions for universal rejection conditions.
Development of the classification
The completeness framework originated with Stephen Cook’s 1971 proof that Boolean satisfiability is NP-complete. Leonid Levin independently developed an equivalent theory of universal computational problems, and Richard Karp subsequently established polynomial-time reductions from satisfiability to a broad family of combinatorial decision problems. These results supplied the reduction theory from which complementary completeness follows.
In 1973, You Watanabe formulated co-NP-completeness explicitly in terms of polynomial-time many-one reductions and identified propositional tautology as the complement-dual of satisfiability. This formulation separated co-NP-hardness from membership in co-NP and fixed the terminology used for complete problems in the complementary class. The resulting definition is equivalent to classifying a language as co-NP-complete whenever its complement is NP-complete.
The term does not imply that co-NP is the set-theoretic complement of NP. Both are classes of languages, and they can overlap. The notation instead means that co-NP contains the complements of languages in NP: [ \mathrm{co\text{-}NP={L\mid \overline{L}\in NP}}. ]
Relation to complexity-class separations
Every language in P belongs to both NP and co-NP because deterministic polynomial-time computation is closed under exchanging acceptance and rejection. Thus, [ \mathrm{P}\subseteq \mathrm{NP}\cap\mathrm{co\text{-}NP}. ]
No co-NP-complete problem is known to belong to P. If any co-NP-complete language were in P, its NP-complete complement would also be in P, which would imply [ \mathrm{P}=\mathrm{NP}=\mathrm{co\text{-}NP}. ] The converse inclusion between NP and co-NP is likewise unresolved. If an NP-complete language belonged to co-NP, closure under polynomial-time reductions would imply (\mathrm{NP}=\mathrm{co\text{-}NP}).
Equality between NP and co-NP would not by itself establish (\mathrm{P}=\mathrm{NP}). It would instead show that polynomially verifiable certificates exist for both membership and nonmembership throughout NP. Under that equality, NP-complete and co-NP-complete languages would coincide as completeness classes under polynomial-time many-one reductions.
Connection with proof complexity
Co-NP-completeness has a direct interpretation in proof complexity, particularly through propositional tautologies. Stephen Cook and Robert Reckhow formalized a propositional proof system as a polynomial-time computable mechanism whose range is exactly the set of tautologies. A proof system is polynomially bounded when every tautology has a proof whose length is bounded by a polynomial in the formula length.
The existence of a polynomially bounded propositional proof system is equivalent to (\mathrm{NP}=\mathrm{co\text{-}NP}). If such a system exists, short proofs serve as NP certificates for TAUT, placing this co-NP-complete language in NP. Conversely, if NP equals co-NP, tautologies possess polynomially bounded certificates that can be represented within an appropriate proof system.
This correspondence explains the structural role of TAUT beyond its status as a canonical complete language. Lower bounds on particular proof systems describe limitations of those systems, whereas a universal superpolynomial lower bound applying to every propositional proof system would separate NP from co-NP.