Best known algorithm for NEXP-complete problem

For every $\epsilon>0$, there exists an NEXP-complete language $L_\epsilon$ in $\mathrm{NTIME}(2^{n^\epsilon})$, and therefore in $\mathrm{DTIME}(2^{2^{n^\epsilon}})$, which is below $2^{o(2^n)}$.

To see this, fix your favourite NEXP-complete language $L$. Fix $c$ such that $L\in\mathrm{NTIME}(2^{n^c})$, and let $d>c/\epsilon$. Then $$L_\epsilon=\{1^{|x|^d}0x:x\in L\}$$ is NEXP-complete as $L$ reduces to $L_\epsilon$ by the poly-time (or even log-space) reduction $x\mapsto1^{|x|^d}0x$, and it is decidable in $\mathrm{NTIME}(2^{n^\epsilon})$: given an input $w$ of length $n$, we can check in polynomial time whether it is of the form $1^{|x|^d}0x$, and if so, extract $x$, which is of length $|x|<n^{1/d}$. Then, we can test whether $x\in L$ in nondeterminisitic time $2^{|x|^c}<2^{(n^{1/d})^c}=2^{o(n^\epsilon)}$.

Note that the nondeterministic time-hierarchy theorem implies that no NEXP-complete problem is in $\bigcap_{\epsilon>0}\mathrm{NTIME}(2^{n^\epsilon})$. In analogy with the Exponential Time Hypothesis, it seems reasonable to conjecture that the deterministic running times above are the best possible, i.e., there is no NEXP-complete problem in $\bigcap_{\epsilon>0}\mathrm{DTIME}(2^{2^{n^\epsilon}})$.

Solved by user6959 (14,773 )
May 30, 2022 at 08:56