**P** is a subset of both **NP** and **co-NP**. That subset is thought to be strict in both cases. **NP** and **co-NP** are also thought to be unequal. If so, then no **NP-complete** problem can be in **co-NP** and no **co-NP-complete** problem can be in **NP**.

This can be shown as follows. Assume that there is an **NP-complete** problem that is in **co-NP**. Since all problems in **NP** can be reduced to this problem it follows that for all problems in **NP** we can construct a non-deterministic Turing machine that decides the complement of the problem in polynomial time, i.e., **NP** is a subset of **co-NP**. From this it follows that the set of complements of the problems in **NP** is a subset of the set of complements of the problems in **co-NP**, i.e., **co-NP** is a subset of '\*NP . Since we already knew that NP is a subset of co-NP it follows that they are the same. The proof for the fact that no co-NP-complete problem can be in NP*' is symmetrical.

If a problem can be shown to be in both **NP** and **co-NP**, that is generally accepted as strong evidence that the problem is probably not **NP-complete**. One example is integer factorization, the problem of finding the prime factors of a number. It is in both **NP** and **co-NP**, but is generally suspected to be outside **P**, outside **NP**-complete, and outside **co-NP**-complete. PRIMES belonging to P has been proved in 2002 by Manindra Agrawal, Neeraj Kayal and Nitin Saxena (all three from IIT Kanpur, India).