{{Short description|Complexity class}} {{lowercase}} In complexity theory, computational problems that are '''co-NP-complete''' are those that are the hardest problems in co-NP, in the sense that any problem in co-NP can be reformulated as a special case of any co-NP-complete problem with only polynomial overhead. If P is different from co-NP, then all of the co-NP-complete problems are not solvable in polynomial time. 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.

The concept is of particular interest in the study of the P=NP problem, and in NP-completeness. See co-NP and NP-complete for more details.

==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.<ref name="A&B">{{cite book |last1= Arora |first1= Sanjeev |last2= Barak |first2= Boaz |url= https://www.cs.princeton.edu/theory/complexity/ |title= Complexity Theory: A Modern Approach |publisher= Cambridge University Press |date= 2009 |isbn= 978-0-521-42426-4 }}</ref> 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.

The concept of co-NP-completeness is not particularly distinct from the concept of NP-completeness, since every NP problem is trivially convertible to a co-NP problem and vice-versa, by reversing "accept" and "reject". Consequently, every NP-complete problem can be converted to a co-NP complete problem.

This does not mean, however, that the concept of co-NP-completeness is useless, since it is possible that there exists a problem that is NP but not co-NP. Reversing the labels "accept" and "reject" results in a problem that is co-NP but not NP. It is an open problem whether NP=co-NP. Since the problem of P=NP is also open, all known instances of problems in <math>\mathsf{NP} \cap \mathsf{coNP}</math> are stuck in '''P'''.

==Examples== One example of a co-NP-complete problem is checking 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 complementary to the Boolean satisfiability problem, which asks whether there exists ''at least one'' such assignment, and is NP-complete.<ref name="A&B" /> In more detail:

* Given a formula, if it is ''not'' a tautology, then it can be disproven in polynomial time by an explicit assignment. * Given a formula, if it ''is'' satisfiable, then it can be proven in polynomial time by an explicit assignment.

If any sparse language is co-NP-complete (or even just co-NP-hard), then {{nowrap|P = NP}}.<ref>{{cite journal |first=S. |last=Fortune |title=A Note on Sparse Complete Sets |journal=SIAM Journal on Computing |volume=8 |issue=3 |pages=431–433 |year=1979 |doi=10.1137/0208034 |url=https://ecommons.cornell.edu/bitstream/1813/7473/1/78-355.pdf |hdl=1813/7473 |hdl-access=free }}</ref> This result is used in Mahaney's theorem.<ref>{{Citation |last=Hartmanis |first=J. |title=An essay about research on sparse NP complete sets |date=1980 |work=Mathematical Foundations of Computer Science 1980 |volume=88 |pages=40–57 |editor-last=Dembiński |editor-first=P. |url=http://link.springer.com/10.1007/BFb0022494 |place=Berlin/Heidelberg |publisher=Springer-Verlag |language=en |doi=10.1007/bfb0022494 |isbn=978-3-540-10027-0 |last2=Mahaney |first2=S. R.|url-access=subscription }}</ref>

==References== <references />

== External links == * {{CZoo|coNPC|C#conpc}}

{{ComplexityClasses}}

Category:Complexity classes