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)
Thanks for this interesting post. These problem are both tough and intriguing.
Do you know of a recent survey, or compilation of such problems (i.e., problems in NP \cap coNP but not in P, or in NP but not known to be NP-complete)?
Also, (I should know this but…) could you expand on what it means for the “Polynomial Hierarchy” to collapse “to its second level”? I’m familiar with the classes P, NP, co-NP, NP-complete and their relationships. I also know a little about the GI-complete class. Is the merge of GI-complete with NP-complete the “second level collapse” to which you refer?
I don’t know of such survey. I listed the problems (that I know) that are known to be in NP intersect coNP but are not known to be in P.
My favorite example of a problem in NP that is not known to be NP-complete is graceful labeling. Read my earlier post at https://kintali.wordpress.com/2009/06/23/graceful-tree-conjecture/
To understand the definitions and levels of polynomial hierarchy read this article : http://en.wikipedia.org/wiki/Polynomial_hierarchy
Thanks. The “Polynomial hierarchy” concept appears more complicated that I had thought. It appears I’ll need to reserve a fair amount of time for thinking/reading about it.
If “all languages in P are in NP \cap coNP”, then “P \subset(eq) NP \cap coNP”. You may want to say that the inverse inclusion is not true.
I think I left one important qualifier out of my question. I should’ve asked:
Do you know of a recent survey, or compilation of such problems, i.e., problems in NP \cap coNP but not in P, or in NP but not known to be either in P or NP-complete)?
I heard from Len Adleman that NP intersect coNP has no complete problems, given some standard complexity assumptions. However, I can’t seem to find the reference for this, nor figure out which assumptions this statement is based on. I was wondering if you knew!
Also: will you be attending CCC?
NP intersect coNP is a semantic class i.e., given a TM M it is undecidable to check if M accepts a language in NP intersect coNP. More semantic classes are BPP, ZPP. Semantic classes don’t have complete problems, according to the standard notion of completeness.
Well, it seems that *some* semantic classes will have complete problems. For example, if BPP = P as widely believed, then BPP will have a complete problem.
However, I have a very stupid question, then, as I’m trying to understand the difference between semantic and syntactic classes:
How is the set of deterministic, polynomial time Turing machine descriptions decidable? I can see how the set is recursively enumerable, but what about the complement of that set? There are Turing machines that do not halt on all inputs, and trying to determine if these machines will halt in polynomial time does not seem to be possible. I feel like I’m missing something here.
@hyuen You can find the answers to your questions in Papadimitriou’s Computational Complexity Book.
The Two Bicliques Problem is in NP intersection coNP: http://arxiv.org/abs/1104.3463
SIR I’M RESEARCH SCHOLAR FROM INDIA INTERESTED IN WORKING ON GRAPH ISOMORPHISM FOR MULTICORE SYSTEM. CAN YOU PROVIDE CERTAIN GUIDELINE ON THIS AS YOUR CURRENT WORK IS ON GRAPH ISOMORPHISM
Pingback: Reasons to believe $P ne NP cap coNP$ (or not) | Question and Answer
Thanks KINTALI for your post…
Could you answer me the following question, please?
If L1 is NP-complete and L2 is co-NP-complete, Is it true that L1 intersection L2 is DP-complete?
I saw that question in Papadimitriou’s Computational Complexity Book, but I don’t know the answer.
Pingback: Problems Between P and NPC | CL-UAT
Pingback: Problems Between P and NPC | XL-UAT
We all know that Graph Isomorphism can now be solved in quasipolynomial time. But Parity Games too have recently been shown to have quasipolynomial time algorithms. (Seems like problems which can be solved efficiently in practice also have theoretical quasipolynomial time algorithms.)
Извините за то, что вмешиваюсь… Мне знакома эта ситуация. Можно обсудить.