Co-NP-complete

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.

Example

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.

References


Full article ▸

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