It's open whether $EXP = NEXP \to P = NP$ (the other direction can be shown by padding). My question: has there been any progress along these lines at all? For example, can we show that $EXP = NEXP \to NP \subset SUBEXP$ (where $SUBEXP = \cap_{\epsilon > 0} 2^{n^\epsilon}$)?

  • $\begingroup$ Perhaps you will get more responses in cstheory.se. $\endgroup$ – Yuval Filmus Dec 17 '15 at 18:09
  • $\begingroup$ this reminds me of exponential time hypothesis which is probably "close/ related"... $\endgroup$ – vzn Dec 17 '15 at 20:07

If someone has demonstrated that $EXP=NEXP\implies NP\subseteq SUBEXP$, then that guy has unconditionally proved a long-sought separation $P^{NP}\subsetneq NEXP$.

Proof: If $EXP\neq NEXP$, then obviously, $P^{NP}\neq NEXP$.

So assuming $EXP=NEXP$, the above statement gives us $NP\subseteq SUBEXP$. We have:


So, $P^{NP}\subseteq SUBEXP\subsetneq EXP$.$\blacksquare$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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