<p>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.</p>

CC BY-SA 3.0
2011-08-19T02:03:26.030Z
2011-08-19T02:03:26.030Z
Mahdi Cheraghchi
<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-03-09T18:46:46.853Z
2012-03-09T18:46:46.853Z
David Harris
<p>You cannot show that a problem is $\mathsf{NPI}$ without separating $\mathsf{P}$ from $\mathsf{NP}$. </p>

<p>There are artificial problems that can be proven to be in $\mathsf{NPI}$ using <a href="https://cstheory.stackexchange.com/questions/799/generalized-ladners-theorem/863#863">generalizations of Lander's theorem</a> (also see <a href="https://cstheory.stackexchange.com/questions/7639/is-there-a-pspace-intermediate-language/7640#7640">this</a>) <em>assuming</em> that $\mathsf{NP}\neq\mathsf{P}$. </p>

<p>Also <a href="https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/237#comment-20503">padded version of $ \mathsf{NEXP\text{-}complete} $ problems are $\mathsf{NPI}$</a> assuming $ \mathsf{NEXP} \neq \mathsf{EXP} $ (see also <a href="https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc">this</a> and <a href="https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/237#comment-19148">this</a>).</p>

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

<ol>
<li><p>we can show under reasonable assumptions that it is not $\mathsf{NPC}$ yet it is not known to be in $\mathsf{P}$,</p></li>
<li><p>we can show under reasonable assumptions that it is not in $\mathsf{P}$ yet it is not known to be in $\mathsf{NPC}$,</p></li>
</ol>

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

<p>An example of a reasonable assumption is the <a href="http://en.wikipedia.org/wiki/Exponential_time_hypothesis" rel="nofollow noreferrer">exponential time hypothesis</a> (or some of other <a href="http://en.wikipedia.org/wiki/Computational_hardness_assumption" rel="nofollow noreferrer">computational hardness assumptions</a>).</p>

<blockquote>
  <p>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. </p>
</blockquote>

<p>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}$.</p>

CC BY-SA 3.0
2011-08-19T02:18:40.697Z
"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
CC BY-SA 3.0
2012-03-09T03:35:34.437Z
@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
CC BY-SA 3.0
2012-03-09T03:52:23.760Z
@Kaveh, I think he was thinking about the trivial languages ($\emptyset$ and $\{0,1\}^*$), but you exclude them from P.
didest
CC BY-SA 3.0
2012-03-09T04:06:09.047Z
@Diego, well, nothing is reducible to them, but you are right. I will fix it.
Kaveh
CC BY-SA 3.0
2012-03-09T05:08:55.477Z
@Kaveh and Diego: Yes, I was thinking about these trivial languages.
Victor Stafusa
CC BY-SA 3.0
2011-08-19T00:25:39.143Z
2012-03-09T04:06:48.157Z
2017-04-13T12:32:28.167Z
Kaveh
<p>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.</p>

CC BY-SA 3.0
2011-08-19T00:14:12.243Z
"a problem that can be satisfied in polynomial time", I guess you mean "a problem that can be *verified* in polynomial time".
Kaveh
CC BY-SA 3.0
2011-08-19T00:27:54.427Z
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
CC BY-SA 3.0
2011-08-19T00:46:41.383Z
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
CC BY-SA 3.0
2011-08-19T02:59:03.087Z
@kaveh Made all of the edits.  Thanks for another great answer!
Jesse Stern
CC BY-SA 3.0
2012-03-09T19:10:53.440Z
"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
<cc.complexity-theory><complexity-classes><np-intermediate>
Why are NPI problems not all of the same complexity?
Jesse Stern
# Why are NPI problems not all of the same complexity?

(Asked by: username_0 on 2011-08-18)

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.

**Tags:** cc.complexity-theory, complexity-classes, np-intermediate
> **Comments:**
> **username_1**: "a problem that can be satisfied in polynomial time", I guess you mean "a problem that can be *verified* in polynomial time".  
> **username_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  
> **username_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?".  
> **username_0**: @kaveh Made all of the edits.  Thanks for another great answer!  
> **username_3**: "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!  

---

## 3 answers

### Answer by username_1 on 2011-08-19. Score: 20 | Accepted answer

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](https://cstheory.stackexchange.com/questions/799/generalized-ladners-theorem/863#863) (also see [this](https://cstheory.stackexchange.com/questions/7639/is-there-a-pspace-intermediate-language/7640#7640)) *assuming* that $\mathsf{NP}\neq\mathsf{P}$.

Also [padded version of $ \mathsf{NEXP\text{-}complete} $ problems are $\mathsf{NPI}$](https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/237#comment-20503) assuming $ \mathsf{NEXP} \neq \mathsf{EXP} $ (see also [this](https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc) and [this](https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/237#comment-19148)).

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](http://en.wikipedia.org/wiki/Exponential_time_hypothesis) (or some of other [computational hardness assumptions](http://en.wikipedia.org/wiki/Computational_hardness_assumption)).

> 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}$.

> **Comments:**
> **username_5**: "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"?  
> **username_1**: @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.  
> **username_6**: @Kaveh, I think he was thinking about the trivial languages ($\emptyset$ and $\{0,1\}^*$), but you exclude them from P.  
> **username_1**: @Diego, well, nothing is reducible to them, but you are right. I will fix it.  
> **username_7**: @Kaveh and Diego: Yes, I was thinking about these trivial languages.  

---

### Answer by username_3 on 2011-08-19. Score: 12

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.


---

### Answer by username_4 on 2012-03-09. Score: 9

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.


---

