Questions regarding SETH

Question

I read about the strong exponential time hypothesis, which states (as far as I understand) that SAT problem cannot be solved in running time $O(2^{\epsilon n})$ for any $\epsilon < 1$, where $n$ is the number of variables in the formula.

However, for other NPC problems, it is known that such algorithms exist (for example, Hamiltonian cycle).

My question is as follows: it is possible to create a polynomial reduction from Hamiltonian cycle to SAT - proving that Hamiltonian cycle is "harder" than SAT (this is how we were proven that Hamiltonian cycle is NPC). This allegedly imply that when given a SAT instance, I can use the reduction and the Hamiltonian cycle algorithm to achieve exponential algorithm with smaller exponent, in contrast to SETH. Clearly I miss something here.

Regardless of this question: are there any current research efforts towards progress in this problem?

Answer 1

The subtlety comes in where we introduce the notion of "harder". The reduction showing that SAT can be reduced to Hamiltonian Cycle shows that the latter is "harder" up to polynomial factors. In doing the reduction, we may very well increase the variable $n$ in question substantially (by some polynomial). And the canonical reductions do blow it up quite substantially.

So what's the upshot? Suppose that the reduction from a SAT instance with $t$ variables yields a HamCycle instance with $n = p(t)$ vertices for some polynomial $p$. Running some $O(2^{\epsilon n})$ time algorithm on this HamCycle instance takes time $O(2^{\epsilon p(t)})$. If $p(t) \ll t/\epsilon$, you just broke SETH. But in general, $p$ may be larger than that (often not even linear), in which case your reduction takes longer than the naive brute force approach.

Some recent papers actually work asking the same line of reasoning that you do to establish SETH hardness. For example, consider the graph diameter problem, where we are asked to determine how far apart the two furthest nodes on a graph lie (that is, we're asked to compute the maximum over all (u,v) pairs the length of the shortest path between u and v). Roditty and Williams showed that even in the unweighted case, where all edge lengths are 1, the problem is difficult to solve in time $O(n^{1+\epsilon})$ (using your notation with $\epsilon<1$). The way they do this, roughly, is by finding an exponential-time reduction from SAT to GraphDiameter that blows up the number of vertices from $t$ to $O(2^{t/2})$. In this new giant instance, the diameter is 3 if the instance is satisfiable, 2 if not. Thus, if they can solve GraphDiameter in time $O(n^{1+\epsilon})$ (and if the original exponential time reduction is fast enough, which it is), then they can solve SAT with $t$ variables in time $O((2^{t/2})^{1+\epsilon}) = O(2^{\frac{1+\epsilon}{2}t}) = O(2^{\epsilon't})$ for $\epsilon'<1$, breaking SETH. In reality, their reduction works through dominating set first, but the key ideas remain the same.

Answer 2

Cygan, Kratsch and Nederlof give a $(2+\sqrt{2})^{\texttt{pw}} n^{O(1)}$ algorithm for hamiltonicity on graphs with $n$ vertices and pathwidth $\texttt{pw}$ (assuming you are given the pathwidth decomposition). Assuming SETH, they show that the constant $2+\sqrt{2}$ cannot be improved.

Thus their results give a $(2+\sqrt{2})^n n^{O(1)}$ algorithm, and their results plausibly imply that the constant $2+\sqrt{2}$ cannot be improved (assuming SETH). This shows that when you carry out your program starting with the algorithm of Cygan et al., you get a $2^n n^{O(1)}$ algorithm for SAT, so there is no contradiction.