# 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)

In the wikipedia article on Time Complexity 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)}$$?

• This is not exactly what you are asking for but in one of my paper (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 Feb 22 at 16:13

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