AI Glossary / Graphs and symbolic AI / Intermediate

co-NP

Definition

co-NP, usually written coNP, is the class of decision problems whose complementary problems belong to NP. Equivalently, no-instances have polynomial-size certificates that can be checked in polynomial time. The prefix co refers to exchanging yes and no answers for a problem; it does not mean the set of all problems outside NP.

What it means

A decision problem asks a yes-or-no question. For satisfiability, the question is whether a Boolean formula has at least one satisfying assignment. Its complement asks whether no satisfying assignment exists. The latter problem, unsatisfiability, belongs to coNP.
The difference concerns which side has efficiently checkable evidence. A satisfying assignment quickly demonstrates that a formula is not unsatisfiable. Establishing unsatisfiability may require a more substantial argument. This asymmetry motivates the class, but it does not prove that every coNP problem is difficult. Every problem in P belongs to both NP and coNP.

How it works

To show that a decision problem is in coNP, describe a polynomial-size witness for its no-instances and a polynomial-time procedure that verifies that witness. Alternatively, show that its complement is in NP. The size and running time are measured against the length of the encoded input, not merely a convenient numerical parameter.
For a tautology question, a no-certificate is an assignment that makes the formula false. Evaluating the formula on that assignment is efficient. For unsatisfiability, a no-certificate is an assignment that makes the formula true. These are different questions, although both lie in coNP. Membership says something about available verification structure; it does not specify the algorithm used on a particular instance.

Three practical examples

• A logic tool asks whether a propositional formula is true for every assignment; one falsifying assignment refutes that claim.
• A configuration analysis asks whether the encoded Boolean constraints admit no configuration; one valid configuration disproves the impossibility claim.
• A graph exercise asks whether a graph has no proper three-coloring; a valid three-coloring is efficiently checkable evidence for a no-answer.

Think of it this way

Think of a statement that every item in a collection meets a condition. A single counterexample can refute it, while confirming it may demand broader reasoning. The analogy captures the certificate asymmetry, but coNP has precise input-size and polynomial-time requirements. Not every everyday universal statement fits a finite decision problem in this class.

Worked example

Let F be the formula (A OR B) AND (NOT A OR B). Ask the coNP-style unsatisfiability question: does F have no satisfying assignment? A proposed certificate for a no-answer is A = false and B = true. The first clause evaluates to true because B is true. The second also evaluates to true. The assignment therefore satisfies F and refutes the claim that F is unsatisfiable.
Now consider G = A AND NOT A. Neither A = false nor A = true satisfies G. In this tiny example, a two-row truth table establishes a yes-answer to unsatisfiability. The fact that this particular yes-instance has a short explanation does not establish polynomial-size certificates for every yes-instance of every coNP problem.
Also, evaluating F on the supplied assignment is not the same task as discovering that assignment. The worked example isolates checking a certificate from searching for one, which is essential to understanding complexity classes.

Illustrative case study

At fictional Alder Rules, a team wants a checker to distinguish no valid configuration from no configuration found yet. During review, an engineer supplies a configuration satisfying the supposedly impossible rule set. The checker can verify it directly and reject the impossibility claim.
The team revises its reporting so a search timeout remains unresolved rather than being labeled impossible. This fictional case illustrates the practical difference between evidence and unsuccessful search. It does not claim that the business's full configuration problem has a particular complexity classification without analyzing its exact representation.

Common misconceptions and mistakes

coNP is not the complement of NP as a collection of problems. It is formed by complementing individual decision problems. NP and coNP share all problems in P, so they are not disjoint.
It is not established that NP and coNP are equal, nor that they are different. Likewise, membership in coNP is not a proof of exponential running time. A simple restricted family may be tractable, and many practical instances may be solved quickly. Finally, a general certificate definition concerns all instances on the relevant side; observing a short proof for one example does not establish a class-wide guarantee.

Business use

The concept helps teams communicate the difference between finding a counterexample and establishing that none exists. In verification and rule analysis, request evidence appropriate to the reported result: a violating assignment, a proof of impossibility, or an explicit unresolved status. Complexity terminology should qualify expectations about general problem families rather than replace benchmarks on the actual workload. Record restrictions that make the business problem easier than its unrestricted logical formulation.

People also ask

Does coNP mean not in NP?

No. It means the complementary decision problem is in NP, and the classes overlap.

Are all coNP problems hard?

No. P is contained in coNP.

Is NP equal to coNP?

This remains an open question in standard complexity theory; the definition does not settle it.

Check your understanding

For the question Is F unsatisfiable?, why is a satisfying assignment a certificate for a no-answer?

Answer: One satisfying assignment proves that F has a solution, directly contradicting the claim that it has none.

Related terms

• Satisfiability
• co-NP-complete
• NP
• P
• decision problem
• polynomial time
• certificate
• complement
• unsatisfiability
• tautology

Learn next

Learn coNP-completeness next. Separate membership, which concerns checkable no-certificates, from hardness, which concerns reductions from other problems. Practice stating both a problem and its complement before assigning a complexity label.

More in Graphs and symbolic AI

• Closed-world assumption - The closed-world assumption is a reasoning convention that treats relevant facts not established by the knowledge base as false.
• Closeness - Closeness, or closeness centrality, measures how near a node is to other nodes in a graph according to shortest-path distances.
• Clutter - Clutter, in tracking and data association, means detections that do not come from the target or targets of interest and instead create nuisance observations.
• Coarse-to-fine - Coarse-to-fine is a strategy that begins with a simplified or lower-detail representation and progressively introduces more detail.
• Cognitive architectures - Cognitive architectures are general frameworks that specify how components such as memory, perception, reasoning, learning, and action selection work...
• Cognitive science - Cognitive science is the interdisciplinary study of mind, cognition, and intelligent behavior.

Sources

Primary sources: James Aspnes, original computational-complexity notes, https://cs.yale.edu/homes/aspnes/classes/468/notes.pdf ; Kevin Wayne, original NP-completeness teaching slides, https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/08NPComplete.pdf . Formula calculations and fictional case are original illustrations.

Previous: Co-domain Next: co-NP-complete