Theoretical Computer Science
cc.complexity-theory conditional-results nexp structural-complexity
Updated Tue, 07 Jun 2022 11:32:56 GMT

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


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




Solution

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







External Links

External links referenced by this document: