What is "co-np-complete"

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 , a critical foundation for Mahaney's theorem.