Theoretical Computer Science
cc.complexity-theory exp-time-algorithms nexp
Updated Tue, 07 Jun 2022 15:06:47 GMT

# Best known algorithm for NEXP-complete problem

What is the best (in time) algorithm for NEXP-complete problems?

Is there an algorithm that solve a NEXP-complete problem in time $$2^{o(2^n)}$$?

## Solution

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