<p><span class="math-container">$\let\R\mathrm$</span>The nondeterministic time hierarchy theorem, which is the reason <span class="math-container">$\R{NP\ne NEXP}$</span> in the first place, immediately gives you infinitely many (even <span class="math-container">$2^{\aleph_0}$</span>) classes intermediate between <span class="math-container">$\R{NP}$</span> and <span class="math-container">$\R{NEXP}$</span>. (I take a “complexity class” to be a class of languages <span class="math-container">$L\subseteq\{0,1\}^*$</span> closed under polynomial-time many-one reducibility and language join.)</p>
<p>For example, for each real <span class="math-container">$\alpha\ge1$</span>, let <span class="math-container">$C_\alpha=\R{NTIME}(2^{O((\log n)^\alpha)})$</span>. It is easy to see that each <span class="math-container">$C_\alpha$</span> is a complexity class, and <span class="math-container">$\R{NP}=C_1\subseteq C_\alpha\subseteq C_\beta\subseteq\R{NEXP}$</span> for <span class="math-container">$\alpha\le\beta$</span> (in fact, all the classes are even within nondeterministic <em>quasipolynomial</em> time). To see that the inclusion <span class="math-container">$C_\alpha\subsetneq C_\beta$</span> is strict for <span class="math-container">$\alpha&lt;\beta$</span>, pick rational <span class="math-container">$\alpha&lt;p&lt;q&lt;\beta$</span> so that <span class="math-container">$2^{(\log n)^q}$</span> is time-constructible; then
<span class="math-container">$$C_\alpha\subseteq\R{NTIME}(2^{(\log n)^p})\subsetneq\R{NTIME}(2^{(\log n)^q})\subseteq C_\beta$$</span>
by the nondeterministic time hierarchy theorem.</p>

CC BY-SA 4.0
2024-05-02T10:34:39.523Z
2024-05-02T10:34:39.523Z
Emil Jeřábek
<p>Ladner's theorem shows that if <span class="math-container">$P$</span> is different from <span class="math-container">$NP$</span> then there are actually infinitely many complexity classes (for polynomial time reducibility) between the two.</p>
<p>I was wondering if this is also true for classes between <span class="math-container">$NP$</span> and <span class="math-container">$NEXP$</span>, with the advantage that here we know the classes are distinct.</p>
<p>The best lead I have is the answer of Ryan Williams to this post <a href="https://cstheory.stackexchange.com/questions/799/generalized-ladners-theorem">Generalized Ladner&#39;s Theorem</a></p>

CC BY-SA 4.0
2024-04-29T20:15:20.370Z
The nondeterministic time hierarchy theorem immediately gives you an infinite hierarchy of classes of the form $\mathrm{NTIME}(f)$ for $f$ between polynomial and exponential.
Emil Jeřábek
CC BY-SA 4.0
2024-05-01T19:01:42.913Z
@EmilJeřábek Post it as answer?
Jean Abou Samra
CC BY-SA 4.0
2024-05-02T15:50:05.667Z
I think this question is interesting and clear, but not a research-level question. This kind of question fits very good for cs.stackexchange. Maybe someone wants to migrate it?
Hermann Gruber
CC BY-SA 4.0
2024-05-02T19:24:44.090Z
@HermannGruber There is no open migration path to cs, hence only a moderator can do it. You can flag it for moderator attention if you wish.
Emil Jeřábek
CC BY-SA 4.0
2024-05-03T06:57:11.200Z
@EmilJeřábek thank you for the hint, I flagged it!
Hermann Gruber
<cc.complexity-theory>
Hierarchy of classes between NP and NEXP
user1868607
# Hierarchy of classes between NP and NEXP

(Asked by: username_0 on 2024-04-29)

Ladner's theorem shows that if $P$ is different from $NP$ then there are actually infinitely many complexity classes (for polynomial time reducibility) between the two.

I was wondering if this is also true for classes between $NP$ and $NEXP$, with the advantage that here we know the classes are distinct.

The best lead I have is the answer of Ryan Williams to this post [Generalized Ladner's Theorem](https://cstheory.stackexchange.com/questions/799/generalized-ladners-theorem)

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: The nondeterministic time hierarchy theorem immediately gives you an infinite hierarchy of classes of the form $\mathrm{NTIME}(f)$ for $f$ between polynomial and exponential.  
> **username_2**: @EmilJeřábek Post it as answer?  
> **username_3**: I think this question is interesting and clear, but not a research-level question. This kind of question fits very good for cs.stackexchange. Maybe someone wants to migrate it?  
> **username_1**: @HermannGruber There is no open migration path to cs, hence only a moderator can do it. You can flag it for moderator attention if you wish.  
> **username_3**: @EmilJeřábek thank you for the hint, I flagged it!  

---

## 1 answers

### Answer by username_1 on 2024-05-02. Score: 3 | Accepted answer

$\let\R\mathrm$The nondeterministic time hierarchy theorem, which is the reason $\R{NP\ne NEXP}$ in the first place, immediately gives you infinitely many (even $2^{\aleph\_0}$) classes intermediate between $\R{NP}$ and $\R{NEXP}$. (I take a “complexity class” to be a class of languages $L\subseteq\{0,1\}^\*$ closed under polynomial-time many-one reducibility and language join.)

For example, for each real $\alpha\ge1$, let $C\_\alpha=\R{NTIME}(2^{O((\log n)^\alpha)})$. It is easy to see that each $C\_\alpha$ is a complexity class, and $\R{NP}=C\_1\subseteq C\_\alpha\subseteq C\_\beta\subseteq\R{NEXP}$ for $\alpha\le\beta$ (in fact, all the classes are even within nondeterministic *quasipolynomial* time). To see that the inclusion $C\_\alpha\subsetneq C\_\beta$ is strict for $\alpha<\beta$, pick rational $\alpha so that $2^{(\log n)^q}$ is time-constructible; then
$$C\_\alpha\subseteq\R{NTIME}(2^{(\log n)^p})\subsetneq\R{NTIME}(2^{(\log n)^q})\subseteq C\_\beta$$
by the nondeterministic time hierarchy theorem.


---

