NP is the set of languages that have short proofs. coNP is the set of languages that have short refutations. Note that coNP is not the complement of NP. NP coNP is non-empty. It is easy to see that all languages in P are in NP coNP i.e., P NP coNP. It is conjectured that P NP coNP. i.e., there are problems in NP coNP that are not in P. Following are some problems in NP coNP that are not known to be in P.
Factoring : Given an integer what is the complexity of finding its factors. Every integer always has a unique factorization. Hence, Factoring is very different from the NP-complete problems. The following exercise states that it is highly unlikely that Factoring is NP-complete. On the other hand if Factoring is in P then the world as we know today will be in chaos !! Factoring is conjectured to be an intermediate problem.
Exercise : If Factoring is NP-complete then NP = coNP.
The first step to solve the above exercise is to show that Factoring is in NP coNP. In fact it is also in UP coUP. Perhaps this is the strongest evidence that P NP coNP.
Parity Games : Deciding which of the two players has a winning strategy in parity games is in NP coNP, as well as in UP coUP.
Stochastic Games : The problem of deciding which player has the greatest chance of winning a stochastic game is in NP coNP [Condon’92]
Lattice Problems : The problems of approximating the shortest and closest vector in a lattice to within a factor of is in NP coNP [AR’05].
All the above problems are not known to be in P.
Open Problems :
- Are there other problems in NP coNP that are not known to be in P.
- PPAD, PLS have been defined to understand problems whose structure is different from NP-complete problems. Can we define new complexity classes to study the complexity of the above mentioned problems (and related problems if any) ?
- Graph Isomorphism (GI) is also conjectured to be an intermediate problem. It is known that GI is not NP-complete unless Polynomial Hierarchy collapses to its second level. Can we improve this result by showing that GI is in coNP ? Whether GI is in coNP is an interesting open problem for a very different reason also. More on this in a future post.
- [Condon’92] Anne Condon: The Complexity of Stochastic Games Inf. Comput. 96(2): 203-224 (1992)
- [AR’05] Dorit Aharonov, Oded Regev: Lattice problems in NP coNP. J. ACM 52(5): 749-765 (2005)