Let S be a set of strings.
Definition. S is CoNP-complete if both of the following hold.
CoNP is a kind of mirror image of NP, where no becomes yes and yes becomes no. Mathematicians say that CoNP is dual to NP.
Theorem. S is NP-complete if and only if S is CoNP-complete.
For example, the problem of determining whether a clausal formula is unsatisfiable is CoNP-complete.
The problem of determining whether a given graph does not have a Hamilton cycle is CoNP-complete.