4
$\begingroup$

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?

Improve this question
$\endgroup$
15
  • 7
    $\begingroup$ Why do you think NPI and NPC should be "symmetric"? Isn't this like your previous question here: cstheory.stackexchange.com/questions/20930/… ? $\endgroup$
    – Huck Bennett
    Commented Sep 5, 2014 at 22:41
  • 3
    $\begingroup$ 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. $\endgroup$
    – Huck Bennett
    Commented Sep 6, 2014 at 3:10
  • 4
    $\begingroup$ 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? $\endgroup$
    – Lance Fortnow
    Commented Sep 6, 2014 at 13:25
  • 3
    $\begingroup$ 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. $\endgroup$
    – Andras Farago
    Commented Sep 6, 2014 at 15:50
  • 3
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Commented Sep 6, 2014 at 17:17

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.