Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?
$\begingroup$
$\endgroup$
10
-
4$\begingroup$ Yes, E=NE implies EXP=NEXP which can be proved using padding argument. $\endgroup$– Mohammad Al-TurkistanyCommented Mar 22, 2012 at 0:33
-
11$\begingroup$ 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? $\endgroup$– Ryan WilliamsCommented Mar 22, 2012 at 1:35
-
2$\begingroup$ And then P = NP if P = 0 or N = 1 ! $\endgroup$– Daniel AponCommented Mar 22, 2012 at 4:48
-
1$\begingroup$ Yes. I guess it is a homework problem. $\endgroup$– Mohammad Al-TurkistanyCommented Mar 22, 2012 at 10:58
-
6$\begingroup$ 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. $\endgroup$– Tsuyoshi ItoCommented Mar 22, 2012 at 22:34
|
Show 5 more comments
1 Answer
$\begingroup$
$\endgroup$
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$).
answered Mar 24, 2012 at 21:17