Editing Co-NP-complete

{{lowercase}}
In [[Computational complexity theory|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 (complexity)|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.

Each co-NP-complete problem is the [[complement (complexity)|complement]] of an [[NP-complete]] problem.  There are some problems in both [[NP (complexity)|NP]] and [[co-NP]], for example all problems in [[P (complexity)|P]] or [[integer factorization]]. However, it is not known if the sets are equal, although inequality is thought more likely. 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 {{nowrap|[[P = NP problem|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> 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 reduction|polynomial-time many-one reducible]] to it.<ref name="A&B">{{cite book |last1= Arora |first1= Sanjeev |last2= Barak |first2= Boaz |url= http://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.

==Example==
One example of a co-NP-complete problem is [[Tautology (logic)|tautology]], the problem of determining whether a given [[Boolean algebra (logic)|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, and is NP-complete.<ref name="A&B"/>

==References==
<references />

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

{{ComplexityClasses}}

[[Category:Complexity classes]]