With P

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

The complexity class P is a subset of both NP and co-NP and inclusion is thought to be 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 proved as follows: If there were a problem in NP-complete and in co-NP at the same time, every NP problem would be reduced to it, it follows that for every NP problem a Turing machine could be built non-deterministic that would decide the complementary problem in polynomial time, that is, NP would be a subset of co-NP and, therefore, the complements of NP would be a subset of the complements of co-NP, that is, 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.