# Why are NPI problems not all of the same complexity?

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.

• "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
• 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
• 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
• "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! – Mahdi Cheraghchi Mar 9 '12 at 19:10

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. 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
• @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. – didest 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
• @Kaveh and Diego: Yes, I was thinking about these trivial languages. – Victor Stafusa Mar 9 '12 at 5:08

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.