I'm interested in the hierarchy of complexity classes between NP and NEXP. I have asked before about this Hierarchy of classes between NP and NEXP and found that already the time hierarchy theorems show there are infinitely many intermediate classes. However, my interest was to know whether there are any intermediate classes that do not form a linear order with the classical complexity classes. One instance of this phenomenon would be a class $C$ such that $C \subseteq NEXP$ but such that neither $PSPACE \subseteq C$ nor $C \subseteq PSPACE$.

  • 1
    $\begingroup$ The classes $\mathrm{NTIME}(f^{O(1)})$ for $f$ a superpolynomial subexponential function are, most likely, incomparable with PSPACE. You cannot prove the existence of such a class incomparable with PSPACE unconditionally (at the current state of art), as it would imply $\mathrm{NP\ne PSPACE\ne NEXP}$. $\endgroup$ May 14 at 10:31


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.