Strong Exponential Time Hypothesis

The iterated logarithm function is defined recursively by

$$\log^*(n) = \begin{cases}0 & n \le 1; \\ \log^*(\log n)+1 & n > 1.\end{cases}$$

For a positive integer $k$, $k$-SAT asks whether a Boolean formula with $n$ variables has a satisfying assignment. Strong Exponential Time Hypothesis. For every $\delta>0$ there is a positive integer $k$ such that $k$-SAT instances with $n$ variables cannot be solved in time $O(2^{n(1-\delta)})$ by a randomized algorithm. SETH is a standard fine-grained complexity assumption underlying conditional lower bounds for the problems studied in the paper.