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.

Each co-NP-complete problem is the complement of an NP-complete problem. There are some problems in both NP and co-NP, for example all problems in 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 P = NP,^{[1]} a critical foundation for Mahaney's theorem.

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.^{[2]} 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.

One example of a co-NP-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, and is NP-complete.^{[2]}

**^**Fortune, S. (1979). "A Note on Sparse Complete Sets" (PDF).*SIAM Journal on Computing*.**8**(3): 431–433. doi:10.1137/0208034. hdl:1813/7473.- ^
^{a}^{b}Arora, Sanjeev; Barak, Boaz (2009).*Complexity Theory: A Modern Approach*. Cambridge University Press. ISBN 978-0-521-42426-4.

Considered feasible | |
---|---|

Suspected infeasible | |

Considered infeasible | |

Class hierarchies | |

Families of classes | |