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}$)?
1 Answer
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:
$$P^{SUBEXP}=SUBEXP$$
So, $P^{NP}\subseteq SUBEXP\subsetneq EXP$.$\blacksquare$