<p>In a quite recent paper <a href="https://arxiv.org/abs/2104.10621" rel="nofollow noreferrer">https://arxiv.org/abs/2104.10621</a> the authors present an algorithm running in time <span class="math-container">$\delta^{2^n}$</span>, where <span class="math-container">$\delta = 1.4423$</span>, for the following <strong>NExpTime</strong>-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 <span class="math-container">$\sqrt{2}^{2^n}$</span>. They also state that they were not aware of any previous algorithms on <strong>NExpTime</strong>-complete problems that had a run time which was significantly lower than <span class="math-container">$2^{2^n}$</span>.</p>
<p><strong>EDIT:</strong> As pointed out by Emil, the authors only state they were not aware of an algorithm for solving the satisfiability problem of an <strong>NExpTime</strong> -complete logic with a run time which was significantly lower than <span class="math-container">$2^{2^n}$</span>.</p>
<p>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.</p>
<p>Let us specify for concreteness that the satisfiability problem of <span class="math-container">$FO^2$</span> can be solved in time <span class="math-container">$2^{2^{n^c}}$</span>, where <span class="math-container">$n$</span> is the length of the input sentence. Consider the following &quot;logic&quot;:
<span class="math-container">$$\mathcal{L} := \{(\theta_\varphi \land \varphi) \mid \varphi \in FO^2\},$$</span>
where for every <span class="math-container">$\varphi$</span> the formula <span class="math-container">$\theta_\varphi$</span> is some arbitrary tautology of length <span class="math-container">$|\varphi|^d$</span>, where <span class="math-container">$d &gt; c/\epsilon$</span>. Clearly the satisfiability problem of this logic is <strong>NExpTime</strong>-complete, since the satisfiability problem of <span class="math-container">$FO^2$</span> can be reduced to it in polynomial time. Furthermore, it is decidable in time <span class="math-container">$2^{2^{n^\epsilon}}$</span>.</p>
<p>Thus, it would seem that even the weaker claim that the authors of <a href="https://arxiv.org/abs/2104.10621" rel="nofollow noreferrer">https://arxiv.org/abs/2104.10621</a> made is &quot;plain nonsense&quot;. However, obviously the authors original claim should be interpretated as follow: they were simply claiming that they were not aware of any &quot;natural&quot; logics with <strong>NExpTime</strong>-complete satisfiability problem for which an algorithm with run time significantly lower than <span class="math-container">$2^{2^n}$</span> existed.</p>

CC BY-SA 4.0
2022-05-30T08:36:48.117Z
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.
Emil Jeřábek
CC BY-SA 4.0
2022-05-30T10:28:54.017Z
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”.
Emil Jeřábek
CC BY-SA 4.0
2022-05-30T10:37:31.260Z
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).
Reijo Jaakkola
CC BY-SA 4.0
2022-05-30T10:41:05.807Z
I wrote “such as”.
Emil Jeřábek
CC BY-SA 4.0
2022-05-30T10:44:04.307Z
And I was referring to your term "syntactic complexity parameter".
Reijo Jaakkola
CC BY-SA 4.0
2022-05-30T07:27:20.497Z
2022-05-30T09:58:40.590Z
2022-05-30T09:58:40.590Z
Reijo Jaakkola
<p>For every <span class="math-container">$\epsilon&gt;0$</span>, there exists an NEXP-complete language <span class="math-container">$L_\epsilon$</span> in <span class="math-container">$\mathrm{NTIME}(2^{n^\epsilon})$</span>, and therefore in <span class="math-container">$\mathrm{DTIME}(2^{2^{n^\epsilon}})$</span>, which is below <span class="math-container">$2^{o(2^n)}$</span>.</p>
<p>To see this, fix your favourite NEXP-complete language <span class="math-container">$L$</span>. Fix <span class="math-container">$c$</span> such that <span class="math-container">$L\in\mathrm{NTIME}(2^{n^c})$</span>, and let <span class="math-container">$d&gt;c/\epsilon$</span>. Then
<span class="math-container">$$L_\epsilon=\{1^{|x|^d}0x:x\in L\}$$</span>
is NEXP-complete as <span class="math-container">$L$</span> reduces to <span class="math-container">$L_\epsilon$</span> by the poly-time (or even log-space) reduction <span class="math-container">$x\mapsto1^{|x|^d}0x$</span>, and it is decidable in <span class="math-container">$\mathrm{NTIME}(2^{n^\epsilon})$</span>: given an input <span class="math-container">$w$</span> of length <span class="math-container">$n$</span>, we can check in polynomial time whether it is of the form <span class="math-container">$1^{|x|^d}0x$</span>, and if so, extract <span class="math-container">$x$</span>, which is of length <span class="math-container">$|x|&lt;n^{1/d}$</span>. Then, we can test whether <span class="math-container">$x\in L$</span> in nondeterminisitic time <span class="math-container">$2^{|x|^c}&lt;2^{(n^{1/d})^c}=2^{o(n^\epsilon)}$</span>.</p>
<p>Note that the nondeterministic time-hierarchy theorem implies that no NEXP-complete problem is in <span class="math-container">$\bigcap_{\epsilon&gt;0}\mathrm{NTIME}(2^{n^\epsilon})$</span>. 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 <span class="math-container">$\bigcap_{\epsilon&gt;0}\mathrm{DTIME}(2^{2^{n^\epsilon}})$</span>.</p>

CC BY-SA 4.0
2022-05-30T08:56:09.903Z
2022-05-30T09:34:38.407Z
2022-05-30T09:34:38.407Z
Emil Jeřábek
<p>What is the best (in time) algorithm for <strong>NEXP</strong>-complete problems?</p>
<p>Is there an algorithm that solve  a <strong>NEXP</strong>-complete problem in time <span class="math-container">$2^{o(2^n)}$</span>?</p>

CC BY-SA 4.0
2022-05-30T06:24:18.437Z
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)}$.
Emil Jeřábek
<cc.complexity-theory><exp-time-algorithms><nexp>
Best known algorithm for NEXP-complete problem
Alexey Milovanov
# Best known algorithm for NEXP-complete problem

(Asked by: username_0 on 2022-05-29)

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

**Tags:** cc.complexity-theory, exp-time-algorithms, nexp

> **Comments:**
> **username_1**: 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)}$.  

---

## 2 answers

### Answer by username_1 on 2022-05-30. Score: 6 | Accepted answer

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


---

### Answer by username_2 on 2022-05-30. Score: 3

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.

> **Comments:**
> **username_1**: 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.  
> **username_1**: 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”.  
> **username_2**: 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).  
> **username_1**: I wrote “such as”.  
> **username_2**: And I was referring to your term "syntactic complexity parameter".  

---

