<p>We can write ${\mathsf {NP}}-{\mathsf P}= {\mathsf {NPC}}\cup {\mathsf {NPI}}$ 
where ${\mathsf {NPC}}$ is the set of ${\mathsf {NP}}$-complete languages (not in ${\mathsf {P}}$ by this partition), and ${\mathsf {NPI}}$ contains the  ${\mathsf {NP}}$-intermediate ones. Assuming ${\mathsf P}\neq  {\mathsf {NP}}$, both ${\mathsf {NPC}}$ and  ${\mathsf {NPI}}$ are known nonempty.</p>

<p>There is, however, a kind of strange asymmetry between ${\mathsf {NPC}}$ and  ${\mathsf {NPI}}$. Under the hypothesis ${\mathsf P}\neq  {\mathsf {NP}}$, we know not only that both sets are nonempty, but we also have plenty of natural problems that are <em>provably</em> in ${\mathsf {NPC}}$. On the other hand, to my knowledge, there is not a single <em>natural</em>  problem that has been proven to fall in ${\mathsf {NPI}}$, under the same ${\mathsf P}\neq  {\mathsf {NP}}$ hypothesis.</p>

<p><em>Note:</em>  Even though there are quite a few natural <em>candidates</em> for ${\mathsf {NPI}}$ status,  none of them has been  proven to be in ${\mathsf {NPI}}$ under the ${\mathsf P}\neq  {\mathsf {NP}}$ hypothesis, as far as I know. The highly artificial construction provided by Ladner's Theorem does not qualify for a natural problem.</p>

<p>Thus, assuming ${\mathsf P}\neq  {\mathsf {NP}}$, the set ${\mathsf {NPC}}$ is teeming with natural examples, while for ${\mathsf {NPI}}$ we do not know even a single natural problem that is <em>guaranteed</em> to fall in the set under the same hypothesis. What could explain this strange asymmetry? Why is ${\mathsf {NPI}}$ so "thin" in this informal sense?</p>

CC BY-SA 3.0
2014-09-05T22:41:54.580Z
Why do you think NPI and NPC should be "symmetric"? Isn't this like your previous question here: http://cstheory.stackexchange.com/questions/20930/why-are-so-few-natural-candidates-for-np-intermediate-status ?
Huck Bennett
CC BY-SA 3.0
2014-09-06T02:33:09.993Z
It is not the same question. The previous question was about natural NPI **candidates**, of which there are plenty. Here the issue is that of the many natural problems in NP, the ones with known complexity status are all either in NPC or in P. Not a single one is known to be in NPI, under the the $P\neq NP$ hypothesis. Of course,  NPC and NPI do not have to be symmetric, but it still seems a little "too asymmetric" to me that **all** natural problems in $NPC\cup NPI$ with known complexity status (under $P\neq NP$)  are actually in NPC.
Andras Farago
CC BY-SA 3.0
2014-09-06T03:10:23.970Z
I think Scott's answer to your last question (particularly the middle paragraph) is great intuition for why that is. I was actually Googling for it as a reference for this question when I realized he had posted it as an answer to your previous question.
Huck Bennett
CC BY-SA 3.0
2014-09-06T11:28:34.943Z
Perhaps the asymmetry is hidden in our intuition of *natural*. It would be interesting if something could be said about the following problem: under the assumption $P \neq NP$, suppose that $M_1,M_2,...$ is an (uncomputable) enumeration of NDTMs in $NP \setminus P$ what is the probability $P(n)$ that a random $M_i,  i \in [1..n]$ falls in NPC.
Marzio De Biasi
CC BY-SA 3.0
2014-09-06T13:25:30.303Z
I'm missing the point here. You are taking the weakest possible assumption that puts NPC problems out of P and wondering why that weak assumption isn't putting weaker problems out of P. Do you think NP-P is "thin" because if we assume P$\neq$PSPACE we can't prove there are any natural problems in NP-P?
Lance Fortnow
CC BY-SA 3.0
2014-09-06T15:50:59.850Z
The weakest possible assumption that puts NPC problems out of P still implies that NPI is nonemtpty (in fact, infinite). Yet, we cannot exhibit any natural problem that must fall in it under the same assumption. This is what I find surprising, since we know many natural examples in the other two parts of NP. Why is NPI so different? The situation with PSPACE is not the same, because P$\neq$PSPACE is not known to imply P$\neq$NP.
Andras Farago
CC BY-SA 3.0
2014-09-06T15:58:46.857Z
That is partly because we don't have an NPI-completeness analog of NP-completeness.
Kaveh
CC BY-SA 3.0
2014-09-06T16:30:36.320Z
If GI is NP-complete then PH collapses to its second level. If we strengthen our assumption that all inclusions in PH are strict then GI must be in NPI. This method could be used to define a weak notion of NPI-completeness, i.e. $A$ is NPI-complete iff the assumption that $A$ is NP-complete implies a collapse of PH.
John D.
CC BY-SA 3.0
2014-09-06T16:58:05.297Z
@user17410, I don't think NPI-completeness would be a good terminology for that property. It lacks the notion of universality that is associated with completeness. (Btw, it seems Andras is not happy with _any_ strengthening of the NPI$\neq\emptyset$ assumption.)
Kaveh
CC BY-SA 3.0
2014-09-06T17:17:12.263Z
Andras, NPI is a "left over" class: we had NP, we took two interesting NP-degrees out of it and called the rest NPI. So I don't see why it is surprising that it is so different from NPC and P.
Kaveh
CC BY-SA 3.0
2014-09-07T01:20:47.067Z
The only way we know of showing a problem that is in NP is ***not*** in P (even assuming various complexity assumptions) is to show that it is NPC. So it's not surprising we don't have any proven separations. For example, we do have plausible arguments that GI and factoring are not NPC, but no arguments for why they aren't in P.
Peter Shor 
CC BY-SA 3.0
2014-09-07T01:43:34.080Z
It is indeed true that in most cases proving NP-completeness is the only way to show that an NP problem is not in P (assuming, of course, P$\neq$NP). But there are some interesting exceptions. A well known example is Unambiguous SAT, which can be (nontrivially) proved to fall in NP-P, under the assumption NP$\neq$RP. Yet, it is not considered likely to be NPC, since that would imply NP=RP.
Andras Farago
CC BY-SA 3.0
2014-09-07T02:24:59.647Z
Sorry, there was a mistake in my previous comment: USAT$\in$NPC is not known to imply NP=RP. The latter would be implied by USAT$\in$P. Still, USAT$\in$NPC is not considered likely, although I am not sure if it is known to cause some unlikely collapse.
Andras Farago
CC BY-SA 3.0
2014-09-07T12:11:08.880Z
Another explanation, though incomplete of course, is given by the theory of Constraint Satisfaction Problems. Lots of *natural* problems can be expressed as CSPs and Schaefer's dichotomy theorem shows that they cannot be intermediate.
Bruno
CC BY-SA 3.0
2014-09-07T17:13:27.190Z
Do you know any NP problem which assuming only NP$\neq$P is provably not in P but the proof does not directly or indirectly rely on its NP-completeness?
Kaveh
<cc.complexity-theory><complexity-classes>
Is there a reason we haven't been able to prove that the existence of natural NPI problems even conditionally under assumption NPI is not empty?
Andras Farago
# Is there a reason we haven't been able to prove that the existence of natural NPI problems even conditionally under assumption NPI is not empty?

(Asked by: username_0 on 2014-09-05)

We can write ${\mathsf {NP}}-{\mathsf P}= {\mathsf {NPC}}\cup {\mathsf {NPI}}$
where ${\mathsf {NPC}}$ is the set of ${\mathsf {NP}}$-complete languages (not in ${\mathsf {P}}$ by this partition), and ${\mathsf {NPI}}$ contains the ${\mathsf {NP}}$-intermediate ones. Assuming ${\mathsf P}\neq {\mathsf {NP}}$, both ${\mathsf {NPC}}$ and ${\mathsf {NPI}}$ are known nonempty.

There is, however, a kind of strange asymmetry between ${\mathsf {NPC}}$ and ${\mathsf {NPI}}$. Under the hypothesis ${\mathsf P}\neq {\mathsf {NP}}$, we know not only that both sets are nonempty, but we also have plenty of natural problems that are *provably* in ${\mathsf {NPC}}$. On the other hand, to my knowledge, there is not a single *natural* problem that has been proven to fall in ${\mathsf {NPI}}$, under the same ${\mathsf P}\neq {\mathsf {NP}}$ hypothesis.

*Note:* Even though there are quite a few natural *candidates* for ${\mathsf {NPI}}$ status, none of them has been proven to be in ${\mathsf {NPI}}$ under the ${\mathsf P}\neq {\mathsf {NP}}$ hypothesis, as far as I know. The highly artificial construction provided by Ladner's Theorem does not qualify for a natural problem.

Thus, assuming ${\mathsf P}\neq {\mathsf {NP}}$, the set ${\mathsf {NPC}}$ is teeming with natural examples, while for ${\mathsf {NPI}}$ we do not know even a single natural problem that is *guaranteed* to fall in the set under the same hypothesis. What could explain this strange asymmetry? Why is ${\mathsf {NPI}}$ so "thin" in this informal sense?

**Tags:** cc.complexity-theory, complexity-classes
> **Comments:**
> **username_1**: Why do you think NPI and NPC should be "symmetric"? Isn't this like your previous question here: http://cstheory.stackexchange.com/questions/20930/why-are-so-few-natural-candidates-for-np-intermediate-status ?  
> **username_0**: It is not the same question. The previous question was about natural NPI **candidates**, of which there are plenty. Here the issue is that of the many natural problems in NP, the ones with known complexity status are all either in NPC or in P. Not a single one is known to be in NPI, under the the $P\neq NP$ hypothesis. Of course,  NPC and NPI do not have to be symmetric, but it still seems a little "too asymmetric" to me that **all** natural problems in $NPC\cup NPI$ with known complexity status (under $P\neq NP$)  are actually in NPC.  
> **username_1**: I think Scott's answer to your last question (particularly the middle paragraph) is great intuition for why that is. I was actually Googling for it as a reference for this question when I realized he had posted it as an answer to your previous question.  
> **username_2**: Perhaps the asymmetry is hidden in our intuition of *natural*. It would be interesting if something could be said about the following problem: under the assumption $P \neq NP$, suppose that $M_1,M_2,...$ is an (uncomputable) enumeration of NDTMs in $NP \setminus P$ what is the probability $P(n)$ that a random $M_i,  i \in [1..n]$ falls in NPC.  
> **username_3**: I'm missing the point here. You are taking the weakest possible assumption that puts NPC problems out of P and wondering why that weak assumption isn't putting weaker problems out of P. Do you think NP-P is "thin" because if we assume P$\neq$PSPACE we can't prove there are any natural problems in NP-P?  
> **username_0**: The weakest possible assumption that puts NPC problems out of P still implies that NPI is nonemtpty (in fact, infinite). Yet, we cannot exhibit any natural problem that must fall in it under the same assumption. This is what I find surprising, since we know many natural examples in the other two parts of NP. Why is NPI so different? The situation with PSPACE is not the same, because P$\neq$PSPACE is not known to imply P$\neq$NP.  
> **username_4**: That is partly because we don't have an NPI-completeness analog of NP-completeness.  
> **username_5**: If GI is NP-complete then PH collapses to its second level. If we strengthen our assumption that all inclusions in PH are strict then GI must be in NPI. This method could be used to define a weak notion of NPI-completeness, i.e. $A$ is NPI-complete iff the assumption that $A$ is NP-complete implies a collapse of PH.  
> **username_4**: @user17410, I don't think NPI-completeness would be a good terminology for that property. It lacks the notion of universality that is associated with completeness. (Btw, it seems Andras is not happy with _any_ strengthening of the NPI$\neq\emptyset$ assumption.)  
> **username_4**: Andras, NPI is a "left over" class: we had NP, we took two interesting NP-degrees out of it and called the rest NPI. So I don't see why it is surprising that it is so different from NPC and P.  
> **username_6**: The only way we know of showing a problem that is in NP is ***not*** in P (even assuming various complexity assumptions) is to show that it is NPC. So it's not surprising we don't have any proven separations. For example, we do have plausible arguments that GI and factoring are not NPC, but no arguments for why they aren't in P.  
> **username_0**: It is indeed true that in most cases proving NP-completeness is the only way to show that an NP problem is not in P (assuming, of course, P$\neq$NP). But there are some interesting exceptions. A well known example is Unambiguous SAT, which can be (nontrivially) proved to fall in NP-P, under the assumption NP$\neq$RP. Yet, it is not considered likely to be NPC, since that would imply NP=RP.  
> **username_0**: Sorry, there was a mistake in my previous comment: USAT$\in$NPC is not known to imply NP=RP. The latter would be implied by USAT$\in$P. Still, USAT$\in$NPC is not considered likely, although I am not sure if it is known to cause some unlikely collapse.  
> **username_7**: Another explanation, though incomplete of course, is given by the theory of Constraint Satisfaction Problems. Lots of *natural* problems can be expressed as CSPs and Schaefer's dichotomy theorem shows that they cannot be intermediate.  
> **username_4**: Do you know any NP problem which assuming only NP$\neq$P is provably not in P but the proof does not directly or indirectly rely on its NP-completeness?  

---

## 0 answers

