9
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ Yes, E=NE implies EXP=NEXP which can be proved using padding argument. $\endgroup$ – Mohammad Al-Turkistany Mar 22 '12 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 Williams Mar 22 '12 at 1:35
  • 2
    $\begingroup$ And then P = NP if P = 0 or N = 1 ! $\endgroup$ – Daniel Apon Mar 22 '12 at 4:48
  • 1
    $\begingroup$ Yes. I guess it is a homework problem. $\endgroup$ – Mohammad Al-Turkistany Mar 22 '12 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 Ito Mar 22 '12 at 22:34
18
$\begingroup$

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$).

$\endgroup$

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.