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$\begingroup$ "a problem that can be satisfied in polynomial time", I guess you mean "a problem that can be verified in polynomial time". $\endgroup$– KavehCommented Aug 19, 2011 at 0:14
-
2$\begingroup$ There is a class of GI-complete problems which are polynomially equivalent to Graph Isomorphism. GI is major problem conjectured to be NP-intermediate $\endgroup$– Mohammad Al-TurkistanyCommented Aug 19, 2011 at 0:27
-
1$\begingroup$ 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?". $\endgroup$– KavehCommented Aug 19, 2011 at 0:46
-
$\begingroup$ @kaveh Made all of the edits. Thanks for another great answer! $\endgroup$– Jesse SternCommented Aug 19, 2011 at 2:59
-
1$\begingroup$ "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! $\endgroup$– Mahdi CheraghchiCommented Mar 9, 2012 at 19:10
3 Answers
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$\begingroup$ "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"? $\endgroup$ Commented Aug 19, 2011 at 2:18
-
$\begingroup$ @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. $\endgroup$– KavehCommented Mar 9, 2012 at 3:35
-
$\begingroup$ @Kaveh, I think he was thinking about the trivial languages ($\emptyset$ and $\{0,1\}^*$), but you exclude them from P. $\endgroup$– didestCommented Mar 9, 2012 at 3:52
-
$\begingroup$ @Diego, well, nothing is reducible to them, but you are right. I will fix it. $\endgroup$– KavehCommented Mar 9, 2012 at 4:06
-
$\begingroup$ @Kaveh and Diego: Yes, I was thinking about these trivial languages. $\endgroup$ Commented Mar 9, 2012 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.
