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

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.