How does one look at a problem and reason that it is likely NP-Intermediate as opposed to NP-Complete? It is often pretty simple to look at a problem and tell whether it is likely NP-Complete or not but it appears to me to be much harder to tell whether a problem is NP-Intermediate as the line seems to be quite thin between the two classes. Basically what I am asking is why would a problem that can be verified in polynomial time (if at all) but not solved in polynomial time (as long as P dosn't equal NP) not be polynomial time reducible to each other. Also, is there some way to show a problem is NP-Intermediate similar to how a problem is shown to be NP-Hard, such as reduction or some other technique? Any links or textbooks that would help me understand the class of NP-Intermediate would be appreciated as well.

  • 2
    "a problem that can be satisfied in polynomial time", I guess you mean "a problem that can be verified in polynomial time". – Kaveh Aug 19 '11 at 0:14
  • 2
    There is a class of GI-complete problems which are polynomially equivalent to Graph Isomorphism. GI is major problem conjectured to be NP-intermediate – Mohammad Al-Turkistany Aug 19 '11 at 0:27
  • 1
    Btw, the title is misleading, equality of two complexity problems with respect to a reduction (e.g. Karp reductions) are already defined, I would suggest you change it to something like "Why NPI problems are not all of the same complexity?". – Kaveh Aug 19 '11 at 0:46
  • @kaveh Made all of the edits. Thanks for another great answer! – Jesse Stern Aug 19 '11 at 2:59
  • 1
    "It is often pretty simple to look at a problem and tell whether it is likely NP-Complete or not". IMHO, that couldn't be farther from truth! – MCH Mar 9 '12 at 19:10
up vote 19 down vote accepted

You cannot show that a problem is $\mathsf{NPI}$ without separating $\mathsf{P}$ from $\mathsf{NP}$.

There are artificial problems that can be proven to be in $\mathsf{NPI}$ using generalizations of Lander's theorem (also see this) assuming that $\mathsf{NP}\neq\mathsf{P}$.

Also padded version of $ \mathsf{NEXP\text{-}complete} $ problems are $\mathsf{NPI}$ assuming $ \mathsf{NEXP} \neq \mathsf{EXP} $ (see also this and this).

A problem in $\mathsf{NP}$ is often conjectured to be $\mathsf{NPI}$ when:

  1. we can show under reasonable assumptions that it is not $\mathsf{NPC}$ yet it is not known to be in $\mathsf{P}$,

  2. we can show under reasonable assumptions that it is not in $\mathsf{P}$ yet it is not known to be in $\mathsf{NPC}$,

and sometime just when we cannot show that it is in $\mathsf{NPC}$ or $\mathsf{P}$.

An example of a reasonable assumption is the exponential time hypothesis (or some of other computational hardness assumptions).

Basically what I am asking is why would a problem that can be satisfied in polynomial time (if at all) but not solved in polynomial time (as long as P doesn't equal NP) not be polynomial time reducible to each other.

I don't see why one would expect that to be true. But in any case, assuming $\mathsf{NPC}\not \subseteq \mathsf{P}$ it follows from Lander's theorem that there are infinitely many levels of $\mathsf{P}$-degrees between $\mathsf{P}$ and $\mathsf{NP}$.

  • 2
    "2. we can show under reasonable assumptions that it is not in P yet it is not known to be in NP" Don't you mean "...in NPC"? – Tyson Williams Aug 19 '11 at 2:18
  • @Tyson Williams: yes, fixed, thanks. – Kaveh Aug 19 '11 at 2:28
  • @Victor, no, it is not known that $\mathsf{P}$ is not equal to $\mathsf{NPC}$, and they are different iff $\mathsf{P}$ and $\mathsf{NP}$ are different. Rolling back your edit. – Kaveh Mar 9 '12 at 3:35
  • @Kaveh, I think he was thinking about the trivial languages ($\emptyset$ and $\{0,1\}^*$), but you exclude them from P. – Diego de Estrada Mar 9 '12 at 3:52
  • @Diego, well, nothing is reducible to them, but you are right. I will fix it. – Kaveh Mar 9 '12 at 4:06

A typical case is when a problem in $\mathsf{NP}$ also lies in $\mathsf{coNP}$ or $\mathsf{coAM}$. Assuming that the polynomial hierarchy does not collapse, such a problem cannot be $\mathsf{NP}$-complete. Examples include integer factorization, discrete logarithm, graph isomorphism, some lattice problems, etc.

Another typical case of $NPI$ problem is when there is a witness of length $\omega(\log n)$ but smaller than $n^{O(1)}$. The problem of the existence of a clique of size $\log n$ in a graph is a typical example -- in this case, the witness (the specific clique) requires $O(\log^2 n)$ bits.

Assuming the Exponential Time Hypothesis, such a problem is easier than an $NP$-complete problem (which requires time $\exp(n^{O(1)})$) but harder than a polynomial time problem.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.