<p>Yes, an example is:<br/>
Accept <span class="math-container">$0^k 1^m$</span> iff <span class="math-container">$k&gt;0$</span> and the <span class="math-container">$k$</span>th Turing machine halts in less than <span class="math-container">$2^{m/k}$</span> steps on the empty input.  Other strings are rejected.  See question <a href="https://cstheory.stackexchange.com/questions/39101/does-%E2%88%A9-%CE%B50-mathrmdtimeon2%CE%B5-mathrmdtimen2o1">Does <span class="math-container">$∩_{ε&gt;0} \mathrm{DTIME}(O(n^{2+ε})) = \mathrm{DTIME}(n^{2+o(1)})$</span>?</a> for the proof.</p>

<p>I expect that there is a relativization barrier against proving equivalence of ETH with its weakening using <span class="math-container">$2^{o(n)}$</span>, and that there are oracles relative to which (note that this is not ETH) for every <span class="math-container">$ε&gt;0$</span> every relativized NP-complete problem can be solved in time <span class="math-container">$O(2^{n^ε})$</span> but not in time <span class="math-container">$2^{n^{o(1)}}$</span>.</p>

CC BY-SA 4.0
2019-02-26T01:14:07.293Z
2019-02-26T01:14:07.293Z
Dmytro Taranovsky
<p>In the wikipedia article on <a href="https://en.wikipedia.org/wiki/Time_complexity#Exponential_time_hypothesis" rel="noreferrer">Time Complexity</a> it is written that:</p>

<blockquote>
  <p>The <strong>exponential time hypothesis (ETH)</strong> is that 3SAT, the satisfiability problem of Boolean formulas in conjunctive normal form with, at most, three literals per clause and with n variables, cannot be solved in time <span class="math-container">$2^{o(n)}$</span>. More precisely, the hypothesis is that there is some absolute constant <span class="math-container">$c&gt;0$</span> such that 3SAT cannot be decided in time <span class="math-container">$2^{cn}$</span> by any deterministic Turing machine. </p>
</blockquote>

<p>We have <span class="math-container">$2^{o(n)} = \bigcap_{c &gt; 0} O(2^{cn})$</span>. </p>

<p><em>Proof</em>: For the inclusion <span class="math-container">$2^{o(n)} \subseteq \bigcap_{c &gt; 0} O(2^{cn})$</span>.
Let <span class="math-container">$f \in o(n)$</span>, then we know that for each <span class="math-container">$c &gt; 0$</span> we can find an <span class="math-container">$N_c$</span> such that for <span class="math-container">$n &gt; N_c$</span> we have <span class="math-container">$f(n) &lt; cn$</span>, or <span class="math-container">$2^{f(n)} &lt; 2^{cn}$</span> which gives this inclusion. For the inclusion <span class="math-container">$\bigcap_{c &gt; 0} O(2^{cn}) \subseteq 2^{o(f)}$</span>. Let be some function <span class="math-container">$g : \mathbb N \to \mathbb N \in \bigcap_{c &gt; 0} O(2^{cn})$</span>, i.e., for each <span class="math-container">$c &gt; 0$</span> we have some <span class="math-container">$N_c$</span> such that for <span class="math-container">$n &gt; N_c$</span> we have <span class="math-container">$g(n) &lt; 2^{cn}$</span>. Taking logarithms this gives <span class="math-container">$\log g(n) &lt; cn$</span>. So we have <span class="math-container">$\log g(n) \in o(n)$</span>.</p>

<p>But ETH is about algorithms, so if we can find for each <span class="math-container">$c &gt; 0$</span> <strong>some</strong> algorithm running in time <span class="math-container">$O(2^{cn})$</span>, this does not imply that we have a single algorithm running in the intersection of those times, i.e., in <span class="math-container">$2^{o(n)}$</span> by the above. So there is still the possiblity that we cannot solve a problem in <span class="math-container">$2^{o(n)}$</span>, but we can solve it by giving for each <span class="math-container">$c &gt; 0$</span> some algorithm <span class="math-container">$A_c$</span> that solves it in <span class="math-container">$O(2^{cn})$</span>. So claiming that something is not solvable in <span class="math-container">$2^{o(n)}$</span> is actually a stronger claim than saying we have a <span class="math-container">$c &gt; 0$</span> such that the problem cannot be solved in <span class="math-container">$O(2^{cn})$</span>. </p>

<p>But is there any example of such a problem, i.e. a problem such that for each <span class="math-container">$c &gt; 0$</span> we have an algorithm (deterministic TM) running in time <span class="math-container">$O(2^{cn})$</span>, but we cannot give an algorithm running in time <span class="math-container">$2^{o(n)}$</span>?</p>

CC BY-SA 4.0
2019-02-22T16:13:19.220Z
This is not exactly what you are asking for but in one of my paper (https://arxiv.org/abs/1703.01928, Section 4) with Yann Strozecki, we prove that if ETH holds then a hierarchy is strict. We do this by contradiction by constructing for some $c < 1$, a $2^{c^i n}$ time algorithm for SAT for every $i$. So we disprove ETH if the hierarchy is not strict but not by constructing a $2^{o(n)}$ algorithm for SAT.
holf
<cc.complexity-theory><ds.algorithms><complexity-classes><time-complexity><sat>
Example problem that is not in $2^{o(n)}$ but could be solved in $O(2^{cn})$ for any $c > 0$ (suggested by wording of ETH)
StefanH
# Example problem that is not in $2^{o(n)}$ but could be solved in $O(2^{cn})$ for any $c > 0$ (suggested by wording of ETH)

(Asked by: username_0 on 2019-02-22)

In the wikipedia article on [Time Complexity](https://en.wikipedia.org/wiki/Time_complexity#Exponential_time_hypothesis) it is written that:

> The **exponential time hypothesis (ETH)** is that 3SAT, the satisfiability problem of Boolean formulas in conjunctive normal form with, at most, three literals per clause and with n variables, cannot be solved in time $2^{o(n)}$. More precisely, the hypothesis is that there is some absolute constant $c>0$ such that 3SAT cannot be decided in time $2^{cn}$ by any deterministic Turing machine.

We have $2^{o(n)} = \bigcap\_{c > 0} O(2^{cn})$.

*Proof*: For the inclusion $2^{o(n)} \subseteq \bigcap\_{c > 0} O(2^{cn})$.
Let $f \in o(n)$, then we know that for each $c > 0$ we can find an $N\_c$ such that for $n > N\_c$ we have $f(n) < cn$, or $2^{f(n)} < 2^{cn}$ which gives this inclusion. For the inclusion $\bigcap\_{c > 0} O(2^{cn}) \subseteq 2^{o(f)}$. Let be some function $g : \mathbb N \to \mathbb N \in \bigcap\_{c > 0} O(2^{cn})$, i.e., for each $c > 0$ we have some $N\_c$ such that for $n > N\_c$ we have $g(n) < 2^{cn}$. Taking logarithms this gives $\log g(n) < cn$. So we have $\log g(n) \in o(n)$.

But ETH is about algorithms, so if we can find for each $c > 0$ **some** algorithm running in time $O(2^{cn})$, this does not imply that we have a single algorithm running in the intersection of those times, i.e., in $2^{o(n)}$ by the above. So there is still the possiblity that we cannot solve a problem in $2^{o(n)}$, but we can solve it by giving for each $c > 0$ some algorithm $A\_c$ that solves it in $O(2^{cn})$. So claiming that something is not solvable in $2^{o(n)}$ is actually a stronger claim than saying we have a $c > 0$ such that the problem cannot be solved in $O(2^{cn})$.

But is there any example of such a problem, i.e. a problem such that for each $c > 0$ we have an algorithm (deterministic TM) running in time $O(2^{cn})$, but we cannot give an algorithm running in time $2^{o(n)}$?

**Tags:** cc.complexity-theory, ds.algorithms, complexity-classes, time-complexity, sat
> **Comments:**
> **username_1**: This is not exactly what you are asking for but in one of my paper (https://arxiv.org/abs/1703.01928, Section 4) with Yann Strozecki, we prove that if ETH holds then a hierarchy is strict. We do this by contradiction by constructing for some $c < 1$, a $2^{c^i n}$ time algorithm for SAT for every $i$. So we disprove ETH if the hierarchy is not strict but not by constructing a $2^{o(n)}$ algorithm for SAT.  

---

## 1 answers

### Answer by username_2 on 2019-02-26. Score: 5 | Accepted answer

Yes, an example is:  
Accept $0^k 1^m$ iff $k>0$ and the $k$th Turing machine halts in less than $2^{m/k}$ steps on the empty input. Other strings are rejected. See question [Does $∩\_{ε>0} \mathrm{DTIME}(O(n^{2+ε})) = \mathrm{DTIME}(n^{2+o(1)})$?](https://cstheory.stackexchange.com/questions/39101/does-%E2%88%A9-%CE%B50-mathrmdtimeon2%CE%B5-mathrmdtimen2o1) for the proof.

I expect that there is a relativization barrier against proving equivalence of ETH with its weakening using $2^{o(n)}$, and that there are oracles relative to which (note that this is not ETH) for every $ε>0$ every relativized NP-complete problem can be solved in time $O(2^{n^ε})$ but not in time $2^{n^{o(1)}}$.


---

