<p>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.</p>

<p>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". </p>

<p>Something along the lines of what you want is the theorem by Hartmanis, Immerman and Sewelson (<a href="http://dl.acm.org/citation.cfm?id=808769">http://dl.acm.org/citation.cfm?id=808769</a>) 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$). </p>

CC BY-SA 3.0
2012-03-24T21:17:46.643Z
2012-03-24T21:17:46.643Z
Ryan Williams
<p>Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?</p>

CC BY-SA 3.0
2012-03-22T00:33:57.243Z
Yes, E=NE implies EXP=NEXP which can be proved using padding argument.
Mohammad Al-Turkistany
CC BY-SA 3.0
2012-03-22T01:31:59.293Z
Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the [FAQ] for more information.
Kaveh
CC BY-SA 3.0
2012-03-22T01:35:29.300Z
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?
Ryan Williams
CC BY-SA 3.0
2012-03-22T04:48:14.330Z
And then P = NP if P = 0 or N = 1 !
Daniel Apon
CC BY-SA 3.0
2012-03-22T10:58:16.193Z
Yes. I guess it is a homework problem.
Mohammad Al-Turkistany
CC BY-SA 3.0
2012-03-22T17:38:38.193Z
Whoops had it reversed.
argentpepper
CC BY-SA 3.0
2012-03-22T22:34:11.123Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-24T23:50:14.627Z
I closed it because it appeared that the OP had made a mistake in posing the question. Maybe I was mistaken.
Suresh Venkat
CC BY-SA 3.0
2012-03-25T02:20:17.037Z
@Suresh: Yes, the asker had made a mistake, but he/she had also corrected the mistake before you closed the question.
Tsuyoshi Ito
<cc.complexity-theory><conditional-results><nexp><structural-complexity>
Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?
argentpepper
# Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?

(Asked by: username_0 on 2012-03-21)

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

**Tags:** cc.complexity-theory, conditional-results, nexp, structural-complexity

> **Comments:**
> **username_1**: Yes, E=NE implies EXP=NEXP which can be proved using padding argument.  
> **username_2**: Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the [FAQ] for more information.  
> **username_3**: 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?  
> **username_4**: And then P = NP if P = 0 or N = 1 !  
> **username_1**: Yes. I guess it is a homework problem.  
> **username_0**: Whoops had it reversed.  
> **username_5**: 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, username_3’s comment can be an answer to it.  
> **username_6**: I closed it because it appeared that the OP had made a mistake in posing the question. Maybe I was mistaken.  
> **username_5**: @Suresh: Yes, the asker had made a mistake, but he/she had also corrected the mistake before you closed the question.  

---

## 1 answers

### Answer by username_3 on 2012-03-24. Score: 21 | Accepted answer

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


---

