Why are NPI problems not all of the same complexity?

Question

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 00: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 00: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 00:46
@kaveh Made all of the edits. Thanks for another great answer! — Jesse Stern, Aug 19 '11 at 02: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 09 '12 at 19:10

score 20 · Accepted Answer · edited Apr 13 '17 at 12:32

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:

we can show under reasonable assumptions that it is not $\mathsf{NPC}$ yet it is not known to be in $\mathsf{P}$,
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 02: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 09 '12 at 03:35
@Kaveh, I think he was thinking about the trivial languages ($\emptyset$ and ${0,1}^*$), but you exclude them from P. — didest, Mar 09 '12 at 03:52
@Diego, well, nothing is reducible to them, but you are right. I will fix it. — Kaveh, Mar 09 '12 at 04:06
@Kaveh and Diego: Yes, I was thinking about these trivial languages. — Victor Stafusa - BozoNaCadeia, Mar 09 '12 at 05:08

score 12 · Answer 2 · answered Aug 19 '11 at 02:03

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.

score 9 · Answer 3 · answered Mar 09 '12 at 18:46

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.

Why are NPI problems not all of the same complexity?

3 Answers3