6
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – holf Feb 22 at 16:13
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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