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

  • 5
    $\begingroup$ By a trivial padding argument, for arbitrarily small $\epsilon>0$, there are NEXP-complete problems in $\mathrm{NTIME}(2^{n^\epsilon})\subseteq\mathrm{DTIME}(2^{2^{n^\epsilon}})$, which is better than $2^{o(2^n)}$. $\endgroup$ Commented May 30, 2022 at 6:24

2 Answers 2


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


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.

  • 1
    $\begingroup$ No, they do not say 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}$. They say “to the best of our knowledge, these are the first exact algorithms for an NEXP-complete decidable logic with run time significantly lower than $O(2^{2^n})$”. That’s quite a different statement, as it only concerns a handful of problems of a very specific nature, not arbitrary NEXP-complete problems. As I already pointed out above, extending the claim to all NEXP-complete problems is plain nonsense. $\endgroup$ Commented May 30, 2022 at 8:36
  • $\begingroup$ I seriously doubt anyone (and authors of that paper in particular) would consider the language you defined to be a “logic”. While the term is vague, in this context it generally denotes fragments of FO or SO obtained by restricting some syntactic complexity parameters such as quantifier alternation, number of variables, or arity of relations. It’s not used as a synonym for “arbitrary set of formulas”. $\endgroup$ Commented May 30, 2022 at 10:28
  • $\begingroup$ I don't think it makes sense to argue about whether or not $\mathcal{L}$ is really a logic, because --- as you pointed out --- the term is quite vague. Note that the sketch of a definition you proposed does not seem to include several natural (decidable) fragments of FO such as the guarded fragment (quantification should be relativized) or unary negation fragment (negation can only be applied to formulas with at most one free variable). $\endgroup$ Commented May 30, 2022 at 10:37
  • $\begingroup$ I wrote “such as”. $\endgroup$ Commented May 30, 2022 at 10:41
  • $\begingroup$ And I was referring to your term "syntactic complexity parameter". $\endgroup$ Commented May 30, 2022 at 10:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.