co-NP

A decision problem X is a member of co-NP if and only if its complement X is in the complexity class NP.

That is, co-NP is the set of decision problems where there exists a polynomial ⁠

Any yes-instance for the original NP problem becomes a no-instance for its complement, and vice versa.

An example of an NP-complete problem is the Boolean satisfiability problem: given a Boolean formula, is it satisfiable (is there a possible input for which the formula outputs true)?

Since this is the complement of the satisfiability problem, a certificate for a no-instance is the same as for a yes-instance from the original NP problem: a set of Boolean variable assignments which make the formula true.

[1] P, the class of polynomial time solvable problems, is a subset of both NP and co-NP.

Because P is closed under complementation, and NP and co-NP are complementary, it cannot be strict in one case and not strict in the other: if P equals NP, it must also equal co-NP, and vice versa.

Suppose for the sake of contradiction there exists an NP-complete problem X that is in co-NP.

Membership in co-NP is also straightforward: one can just list the prime factors of m, all greater or equal to n, which the verifier can confirm to be valid by multiplication and the AKS primality test.