# Hierarchy of classes between NP and NEXP [closed]

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

• 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. Commented Apr 29 at 20:15
• @EmilJeřábek Post it as answer? Commented May 1 at 19:01
• 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? Commented May 2 at 15:50
• @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. Commented May 2 at 19:24
• @EmilJeřábek thank you for the hint, I flagged it! Commented May 3 at 6:57

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