# Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?

Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?

• Yes, E=NE implies EXP=NEXP which can be proved using padding argument. Mar 22 '12 at 0:33
• It's not obvious to me why EXP=NEXP implies E=NE. If that were true, then any $2^{n^k}$-time algorithm for Succinct3SAT can be converted into a $2^{O(n)}$-time algorithm for Succinct3SAT. Maybe you got things reversed, and you meant to ask about the other implication? Mar 22 '12 at 1:35
• And then P = NP if P = 0 or N = 1 ! Mar 22 '12 at 4:48
• Yes. I guess it is a homework problem. Mar 22 '12 at 10:58
• I do not understand the closure of this question as “not a real question” after it was edited to a reasonable question (although the wording of the question is not interesting). For example, Ryan Williams’s comment can be an answer to it. Mar 22 '12 at 22:34

This is open, as far as I know. It could be provable (because its hypothesis may be false) or it just be difficult to show that any $2^{n^k}$-time algorithm for Succinct3SAT can be converted into a $2^{O(n)}$-time algorithm for Succinct3SAT.
In general, theorems of this kind are called "downward collapses" which say if two "large" classes are equal then two "smaller" classes are equal. These theorems are rare. Usually you can either prove an "upward collapse" (small classes equal implies larger classes equal, like $P = NP$ implies $NEXP = EXP$) or its contrapositive, a "downward separation".
Something along the lines of what you want is the theorem by Hartmanis, Immerman and Sewelson (http://dl.acm.org/citation.cfm?id=808769) that $NE = E$ $\iff$ every sparse set in $NP$ is contained in $P$. This gives a "downward collapse" but only for the sparse sets (those sets that contain only $poly(n)$ strings of length $n$).