68 Strong Exponential Time Hypothesis (SETH)

• $q$-SAT: Each clause has at most $q$ literals
• Let $S_q:=\{c:q-\text{SAT can be solved in time }{2}^{c\cdot N}\cdot (N+M{)}^{O(1)}\}$
• Define ${\delta }_q:=$ infimum of the set $S_q$
• Infimum of a set $S$ is the greates number that is $\le$ all elements of $S$

The

${\delta }_3>0$

The

${\lim }_{q\to \infty }{\delta }_q=1$

Consequence

SAT cannot be solved in $(2-ϵ{)}^N\cdot (N+M{)}^{O(1)}$ time for any constant $ϵ>0$

Suppose “Consequence of Strong ETH is not true”.
Suppose SAT has $1.9999^N\cdot (N+M{)}^{O(1)}$ algorithm.
$⟹\forall q\ge 3$, $q$-SAT also has $1.9999^N\cdot (N+M{)}^{O(1)}$ algorithm.
$⟹\forall q\ge 3$, $c^{\star }\in S_q$ where $c^{\star }$ satisfies $2^{c^{\star }}=1.9999$
$⟹\forall q\ge 3$, inf($S_q$) $\le c^{\star }$
$⟹\forall q\ge 3$, ${\delta }_q\le c^{\star }$, this contradicts SETH saying ${\lim }_{q\to \infty }{\delta }_q=1$