Co-NP-complete
In complexity theory, the complexity class Co-NP-complete is the set of problems that are the hardest problems in Co-NP, in the sense that they are the ones most likely not to be in P. If you can find a way to solve a Co-NP-complete problem quickly, then you can use that algorithm to solve all Co-NP problems quickly.
A more 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.
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, then P = NP,[1] a critical foundation for Mahaney's theorem.
References
- ^ S. Fortune. A note on sparse complete sets. SIAM Journal on Computing, volume 8, issue 3, pp.431–433. 1979.
| Important complexity classes (more) |
|---|
| P • NP • co-NP • NP-C • co-NP-C • NP-hard • UP • #P • #P-C • L • NL • NC • P-C • PSPACE • PSPACE-C • EXPTIME • NEXPTIME • EXPSPACE • 2-EXPTIME • PR • RE • Co-RE • RE-C • Co-RE-C • R • BQP • BPP • RP • ZPP • PCP • IP • PH |
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
