0
$\begingroup$

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

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

1 Answer 1

3
$\begingroup$

$\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<p<q<\beta$ 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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.