Best known algorithm for NEXP-complete problem

Question

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

Answer 1

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

Answer 2

In a quite recent paper https://arxiv.org/abs/2104.10621 the authors present an algorithm running in time $\delta^{2^n}$, where $\delta = 1.4423$, for the following NExpTime-complete problem: given a sentence of the two-variable fragment of first-order logic, determine whether it is satisfiable. They also show that unless the strong exponential time hypothesis fails, no algorithm can solve this problem in time $\sqrt{2}^{2^n}$. They also state that they were not aware of any previous algorithms on NExpTime-complete problems that had a run time which was significantly lower than $2^{2^n}$.

EDIT: As pointed out by Emil, the authors only state they were not aware of an algorithm for solving the satisfiability problem of an NExpTime -complete logic with a run time which was significantly lower than $2^{2^n}$.

However, let me also point out that the padding-trick that Emil mentioned works perfectly well also when one is considering the complexity of satisfiability problems.

Let us specify for concreteness that the satisfiability problem of $FO^2$ can be solved in time $2^{2^{n^c}}$, where $n$ is the length of the input sentence. Consider the following "logic": $$\mathcal{L} := \{(\theta_\varphi \land \varphi) \mid \varphi \in FO^2\},$$ where for every $\varphi$ the formula $\theta_\varphi$ is some arbitrary tautology of length $|\varphi|^d$, where $d > c/\epsilon$. Clearly the satisfiability problem of this logic is NExpTime-complete, since the satisfiability problem of $FO^2$ can be reduced to it in polynomial time. Furthermore, it is decidable in time $2^{2^{n^\epsilon}}$.

Thus, it would seem that even the weaker claim that the authors of https://arxiv.org/abs/2104.10621 made is "plain nonsense". However, obviously the authors original claim should be interpretated as follow: they were simply claiming that they were not aware of any "natural" logics with NExpTime-complete satisfiability problem for which an algorithm with run time significantly lower than $2^{2^n}$ existed.