In complexity theory, computational problems that are coNPcomplete are those that are the hardest problems in coNP, in the sense that they are the ones most likely not to be in P. If there exists a way to solve a coNPcomplete problem quickly, then that algorithm can be used to solve all coNP problems quickly.
Each CoNPcomplete problem is the complement of an NPcomplete problem. The two sets are either equal or disjoint. The latter is thought more likely, but this is not known. See coNP and NPcomplete for more details.
Fortune showed in 1979 that if any sparse language is coNPcomplete (or even just coNPhard), then P = NP,^{[1]} a critical foundation for Mahaney's theorem.
Formal definition
A decision problem C is coNPcomplete if it is in coNP and if every problem in coNP is polynomialtime manyone reducible to it. This means that for every CoNP 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 coNP problems in polynomial time.
Example
One simple example of a coNP 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 ▸
