Editing Co-NP-complete (section)

==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.