4

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?

Kaveh
  • 21,577
  • 8
  • 82
  • 183
Andras Farago
  • 11,396
  • 37
  • 70
  • 7
    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 Sep 05 '14 at 22:41
  • 1
    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 Sep 06 '14 at 02:33
  • 3
    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 Sep 06 '14 at 03:10
  • 1
    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 Sep 06 '14 at 11:28
  • 4
    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 Sep 06 '14 at 13:25
  • 3
    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 Sep 06 '14 at 15:50
  • 1
    That is partly because we don't have an NPI-completeness analog of NP-completeness. – Kaveh Sep 06 '14 at 15:58
  • 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. Sep 06 '14 at 16:30
  • @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 Sep 06 '14 at 16:58
  • 3
    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 Sep 06 '14 at 17:17
  • 2
    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 Sep 07 '14 at 01:20
  • 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 Sep 07 '14 at 01:43
  • 2
    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 Sep 07 '14 at 02:24
  • 3
    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 Sep 07 '14 at 12:11
  • 3
    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 Sep 07 '14 at 17:13

0 Answers0