Co-NP

In computational complexity theory, the co-NP complexity class is the set of decision problems complementary to those of the NP class. Complementary problem is understood as one whose positive or negative responses are reversed.

The complexity class P is a subset of both NP and co-NP and it is thought that the inclusion is strict in both cases. It is also thought that NP and co-NP are different. If this is true, no NP-complete problem could be in co-NP and no co-NP-complete problem could be in NP.

This is demonstrated as follows: If there were a problem in NP-complete and in co-NP at the same time, every problem of NP would be reduced in it, it follows that for any problem in NP a Turing machine could be constructed not deterministic to decide the complementary problem in polynomial time, ie, NP would be a subset of co-NP and, therefore, NP complements would be subset of co-NP complements, ie co-NP would be a subset of NP, Therefore NP and co-NP would be the same set. Symmetrically it is shown that no problem in co-NP-complete can be in NP.

wiki