related topics
{math, number, function}

In complexity theory, computational problems that are co-NP-complete are those that are the hardest problems in co-NP, in the sense that they are the ones most likely not to be in P. If there exists a way to solve a co-NP-complete problem quickly, then that algorithm can be used to solve all co-NP problems quickly.

Each Co-NP-complete problem is the complement of an NP-complete problem. The two sets are either equal or disjoint. The latter is thought more likely, but this is not known. See co-NP and NP-complete for more details.

Fortune showed in 1979 that if any sparse language is co-NP-complete (or even just co-NP-hard), then P = NP,[1] a critical foundation for Mahaney's theorem.

Formal definition

A decision problem C is co-NP-complete if it is in co-NP and if every problem in co-NP is polynomial-time many-one reducible to it. This means that for every Co-NP problem L, there exists a polynomial time algorithm which can transform any instance of L into an instance of C with the same truth value. As a consequence, if we had a polynomial time algorithm for C, we could solve all co-NP problems in polynomial time.


One simple example of a co-NP complete problem is tautology, the problem of determining whether a given Boolean formula is a tautology; that is, whether every possible assignment of true/false values to variables yields a true statement. This is closely related to the Boolean satisfiability problem, which asks whether there exists at least one such assignment.


Full article ▸

related documents
Church–Rosser theorem
Measurable function
Power associativity
Prime ideal
Almost all
Equivalence class
Leaf node
Center (group theory)
Sieve of Eratosthenes
Ring homomorphism
Probability axioms
Integer sequence
Digital Signature Algorithm
Gabriel Lamé
Endomorphism ring
Mary (programming language)
Gauss–Legendre algorithm
Krull dimension
Euclidean distance
Markov process
Timeline of programming languages
Disjoint sets
Identity function
Context-sensitive language
Catalan's constant