Co-NP
co-NP, commonly written coNP, is a computational complexity class containing the decision problems whose complementary problems belong to NP. Equivalently, a language lies in co-NP when every no-instance has a certificate whose validity can be checked by a deterministic algorithm in polynomial time. The class formalizes the complexity of efficiently verifying that a proposed object with a specified property does not exist.
The central unresolved question concerning the class is whether NP and co-NP are equal. An equality would imply that polynomially verifiable evidence for existence can always be transformed, at the level of decision problems, into polynomially verifiable evidence for nonexistence. No such general transformation is known, and no separation has been proved.
Formal definition
Let (\Sigma) be a finite alphabet, and let (L \subseteq \Sigma^*) be a formal language. The complement of (L) is
[ \overline{L}=\Sigma^*\setminus L. ]
The class co-NP is defined by
[ \mathrm{coNP}
\left{L \subseteq \Sigma^* \mid \overline{L}\in\mathrm{NP}\right}. ]
Using the verifier definition of NP, a language (L) belongs to co-NP precisely when there are a polynomial (p) and a polynomial-time deterministic verifier (V) such that
[ x\notin L \iff \exists y,\quad |y|\le p(|x|)\ \land\ V(x,y)=1. ]
Thus, the certificate condition applies directly to no-instances of (L). This definition does not exclude the possibility that yes-instances also possess efficiently checkable certificates. Languages for which both kinds of instances have such certificates belong to the intersection (\mathrm{NP}\cap\mathrm{coNP}).
An equivalent bounded-quantifier formulation states that (L\in\mathrm{coNP}) when a polynomial-time predicate (R) and a polynomial (p) exist such that
[ x\in L \iff \forall y,\quad |y|\le p(|x|)\ \Longrightarrow\ R(x,y)=1. ]
The universal quantifier distinguishes this characterization from the corresponding existential characterization of NP.
Development
The conceptual basis of co-NP arose from the formalization of efficient verification and nondeterministic polynomial time. Stephen Cook and Leonid Levin independently established the theory of NP-completeness through work connecting polynomial-time verification with problems capable of representing every computation in NP. Richard Karp subsequently demonstrated that polynomial-time reductions relate a broad family of combinatorial decision problems to this framework.
In 1974, You Watanabe circulated a classification note that applied language complementation systematically to nondeterministic polynomial-time classes and used the designation co-NP for the resulting class. The notation separated complementation of a language from complementation of a computational machine and was incorporated into the terminology of structural complexity theory during the same period.
The resulting framework made NP and co-NP formally symmetric under complementation while preserving their potentially different certificate interpretations. This distinction became central to the study of logical validity, infeasibility certificates, and propositional proof systems.
Relationship with other complexity classes
Every language in P belongs to both NP and co-NP. A deterministic polynomial-time algorithm decides both a language and its complement within the same asymptotic resource bound, giving
[ \mathrm{P}\subseteq \mathrm{NP}\cap\mathrm{coNP}. ]
Complementation exchanges NP and co-NP:
[ L\in\mathrm{NP} \iff \overline{L}\in\mathrm{coNP}, ]
and
[ L\in\mathrm{coNP} \iff \overline{L}\in\mathrm{NP}. ]
Consequently,
[ \mathrm{NP}=\mathrm{coNP} ]
if and only if NP is closed under complement. This equality would not by itself establish (\mathrm{P}=\mathrm{NP}), although the latter equality would immediately imply it.
Both NP and co-NP are contained in PSPACE, because a polynomial-space machine can examine polynomially bounded certificates sequentially without storing an exponentially large search space. They are also situated within the polynomial hierarchy, where NP forms the first existential level and co-NP forms the corresponding universal level:
[ \mathrm{NP}=\Sigma_1^{\mathrm P}, \qquad \mathrm{coNP}=\Pi_1^{\mathrm P}. ]
If NP equals co-NP, the polynomial hierarchy collapses to its first level. This follows because alternating existential and universal polynomially bounded quantifiers would cease to define successively larger classes.
The class co-NP is closed under finite union and finite intersection. These properties follow by taking complements and applying the corresponding closure properties of NP.
Complete problems
A language (A) is co-NP-hard under polynomial-time many-one reductions when every language in co-NP can be transformed into (A) by a polynomial-time computable function preserving membership. It is co-NP-complete when it is both co-NP-hard and a member of co-NP.
The canonical co-NP-complete problem is TAUT, the problem of deciding whether a propositional formula evaluates to true under every assignment. A formula is not a tautology exactly when an assignment making it false exists. Such an assignment has polynomial length and can be checked in polynomial time, placing TAUT in co-NP.
The Boolean satisfiability problem is NP-complete, while its complement, UNSAT, is co-NP-complete. An input to UNSAT is accepted when no satisfying assignment exists. No general polynomial-size certificate of unsatisfiability is known for unrestricted propositional formulas, although restricted formula classes can admit concise certificates or direct polynomial-time algorithms.
Additional co-NP-complete problems arise by expressing universal properties of combinatorial structures. Examples include deciding whether a Boolean circuit computes the constant-one function and determining whether one propositional formula logically implies another. Their completeness follows from polynomial-time transformations of tautology or unsatisfiability.
If any NP-complete language belongs to co-NP, then NP equals co-NP. To see this, every language in NP reduces to that complete language, and co-NP is closed downward under polynomial-time many-one reductions. The symmetric statement holds when a co-NP-complete language belongs to NP.
The intersection of NP and co-NP
The class (\mathrm{NP}\cap\mathrm{coNP}) contains problems for which yes-instances and no-instances both admit polynomially verifiable certificates. Membership in this intersection does not imply that a deterministic polynomial-time decision algorithm is known.
Before the discovery of deterministic polynomial-time primality testing, primality testing provided a prominent example. A composite integer has a nontrivial factorization serving as a certificate of compositeness, while primality has certificates based on the structure of multiplicative groups modulo the integer. The AKS primality test, developed by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, later established that primality belongs to P.
Decision formulations associated with integer factorization also lie in NP and co-NP under standard encodings. Their status illustrates that the intersection can contain problems whose known algorithms have substantially higher running times than polynomial time, even though certificates exist for both answers.
Graph isomorphism belongs to NP because an isomorphism itself provides a verifiable certificate. Its complement therefore belongs to co-NP. The existence of specialized algorithms and interactive protocols gives the problem additional complexity-theoretic structure, but these results do not establish that graph isomorphism belongs to P or that graph nonisomorphism belongs to NP.
Proof complexity
The relationship between co-NP and formal proof systems is most direct for propositional tautologies. A propositional proof system assigns finite proofs to tautologies and permits proof verification in polynomial time. The verification requirement ensures soundness and efficient recognition of valid derivations, while completeness requires every tautology to possess at least one proof.
Stephen Cook and Robert Reckhow formalized this connection through the theory of polynomially checkable propositional proof systems. A proof system is polynomially bounded when every tautology has a proof whose length is bounded by a polynomial in the length of the formula. Such a system exists if and only if
[ \mathrm{NP}=\mathrm{coNP}. ]
The forward direction follows because a polynomial-size proof of tautology would serve as an NP certificate for a co-NP-complete language. For the reverse direction, equality of the classes would give every tautology a polynomially bounded certificate verifiable in polynomial time.
Consequently, lower bounds showing that particular proof systems require long proofs do not by themselves separate NP from co-NP. A separation would require ruling out polynomial bounds for every polynomial-time verifiable propositional proof system.
Oracle dependence
Relativized versions of NP and co-NP can exhibit different relationships depending on the chosen oracle. Oracles exist relative to which the two classes are equal, and other oracles exist relative to which they are unequal. This demonstrates that proof techniques preserved under arbitrary relativization cannot alone resolve the unrelativized equality question.
The oracle results do not determine the relationship between ordinary NP and co-NP. They instead identify a limitation shared by broad classes of diagonalization and simulation arguments.