- Co-NP-complete
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. SeeCo-NP andNP-complete for more details.Fortune showed in 1979 that if any
sparse language isco-NP-complete (or even just co-NP-hard), then P = NP, [S. Fortune. A note on sparse complete sets. "SIAM Journal on Computing", volume 8, issue 3, pp.431–433. 1979.] a critical foundation forMahaney's theorem .Formal definition
A
decision problem "C" is Co-NP-complete if it is inCo-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 theBoolean satisfiability problem , which asks whether there exists "at least one" such assignment.References
Wikimedia Foundation. 2010.