P is a subset of both NP and coNP. That subset is thought to be strict in both cases. NP and coNP are also thought to be unequal. If so, then no NPcomplete problem can be in coNP and no coNPcomplete problem can be in NP.
This can be shown as follows. Assume that there is an NPcomplete problem that is in coNP. Since all problems in NP can be reduced to this problem it follows that for all problems in NP we can construct a nondeterministic Turing machine that decides the complement of the problem in polynomial time, i.e., NP is a subset of coNP. 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 coNP, i.e., coNP is a subset of NP. Since we already knew that NP is a subset of coNP it follows that they are the same. The proof for the fact that no coNPcomplete problem can be in NP is symmetrical.
If a problem can be shown to be in both NP and coNP, that is generally accepted as strong evidence that the problem is probably not NPcomplete. One example is integer factorization, the problem of finding the prime factors of a number. It is in both NP and coNP, but is generally suspected to be outside P, outside NPcomplete, and outside coNPcomplete.
Search Encyclopedia

Featured Article
