67 Exponential Time Hypothesis (ETH)

The CNF-SAT problem

• $N$ variables and $M$ clauses
• Each clause is OR of literals
• Instance of SAT is AND of clauses

Brute Force algorithm runs in $O(2^N\cdot N\cdot M)$ time

• $2^N$ truth assignments
• Each clause has length $\le 2N$
• Need to check if each of the $M$ clauses is satisfied

Infimum of a set $S$ is the greatest number that is $\le$ all elements of $S$

• $S=\{1,2,3,4,5,7,0\}$, inf(S) = 0
• $S=[0,1]$, inf(S) = 0
• $S=(0,1]$, inf(S)=0, because if inf(s) = $ϵ\ge 0$, contradiction as $ϵ/2\in S$

Going back to $q$-SAT for $q\ge 3$

• $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$
• Which number definitely belongs to $S_q$ ? $\to 1\in S_q$ has $2^N\cdot N\cdot M$ algorithm
• Which number does not belongs to $S_q$ ? $\to$ If $0\in S_q$ then $q$-SAT has $(N+M{)}^{O(1)}$ which implies $\mathrm{P}=\mathrm{NP}$ as $q$-SAT is $\mathrm{NP}$-hard , so $0\notin S_q$ (assuming $\mathrm{P}\ne \mathrm{NP}$)

ETH

${\delta }_3>0$

Consequences

$3$-SAT cannot be solved in $2^{o(N)}\cdot (N+M{)}^{O(1)}$ time

Suppose consequence of ETH be true, let $g(n)$ be a function which is $o(n)$ and suppose $3$-SAT has $2^g(n)\cdot (N+M{)}^{O(1)}$ time algorithm.
We want to show that $S_3=(0,1]$. If we can show this then infimum of $S_3$ would be 0, so a contradiction would occur.

$g(n)=o(n)⟹{\lim }_{n\to \infty }\frac{g(n)}{n}=0⟹\forall c>0,\exists n_c,\text{ such that }\forall n\ge n_c,c>\frac{g(n)}{n}$
If we have $2^{g(n)}$ algorithm $⟹$ we also have $2^{c\cdot n}$ algorithm $⟹$ $c\in S_3\forall c>0⟹S_3=(0,1]$

How strong(er) is ETH compared to $\mathrm{P}\ne \mathrm{NP}$

Can you conclude $\mathrm{P}\ne \mathrm{NP}$ (just) assuming the ETH ?

Yes, ETH $⟹$ Consequence of ETH: $3$-SAT has no $2^{o(N)}\cdot (N+M{)}^{O(1)}$ algorithm $⟹$ $3$-SAT has no $(N,M{)}^{O(1)}$ algorithm $⟹$ $\mathrm{P}\ne \mathrm{NP}$ as $3$-SAT is $\mathrm{NP}$-hard

Can you conclude ETH (just) assuming $\mathrm{P}\ne \mathrm{NP}$ ?

We are given $\mathrm{P}\ne \mathrm{NP}$, can you deduce ETH ??
$⟹$ $3$-SAT has no $(N+M{)}^{O(1)}$ algorithm, but this does not rule out $2^{\sqrt{N}}\cdot (N+M{)}^{O(1)}$ algorithm. But $\sqrt{N}$ is $o(N)$, so $2^{\sqrt{N}}\cdot (N+M{)}^{O(1)}=2^{o(N)}\cdot (N+M{)}^{O(1)}$

---

Independent Set

Independent

Given an undirected graph $G=(V,E)$ on $n$ vertices, find a set $X⫅V$ of max size such that no pair of vertices in $X$ forms an edge.

• Instance $I$ of $3$-SAT has a satisfying assignment $⟺$ the graph $G$ has an independent set of size $M$
• $G$ has $3M$ vertices, and for $3$-SAT the value of $M$ can be as large as $\left(\genfrac{}{}{0ex}{}{n}{3}\right)=O(N^3$
• ETH implies no $2^{o(N)}\cdot (N+M{)}^{O(1)}$ time algorithm for $3$-SAT
• Hence, assuming ETH, the Independent Set problem on graphs with $n$ vertices cannot be solved in $2^{o(n^{1/3})}\cdot (N+M{)}^{O(1)}$ time

Sparsification lemma

• In $2^{o(N)}$ time, we can convert a given instance $I$ of $3$-SAT into the $OR$ of $3$-SAT instances $I_1,I_2,\cdots ,I_t$ such that
• $t=2^{o(N)}$
• For each $1\le l\le t$, the instance $I_l$ has
  • Same set of variables as $I$
  • Number of clauses in $I_l$ is $O(N)$

Sparsification

$3$-SAT cannot be solved in $2^{o(N+M)}\cdot (N+M{)}^{O(1)}$ time

In the reduction $3$-SAT ${\le }_p$ Independent Set, we had

• Instance $I$ of $3$-SAT has a satisfying assignment $⟺$ the graph $G$ has an independent set of size $M$
• $G$ has $3M$ vertices
• ETH + Sparsification Lemma implies no $2^{o(N+M)}\cdot (N+M{)}^{O(1)}$ time algorithm for $3$-SAT
• Hence, assuming ETH, the Independent Set problem on graphs with $n$ vertices cannot be solved in $2^{o(n)}\cdot n^{O(1)}$ time

$k$-Vertex Cover

• The goal is only to check whether or not there is a vertex cover of size $\le k$
• We designed a binary-search tree based algorithm running in $2^O(k)\cdot n^{O(1)}$ time on graphs with $n$-vertices
• Can we get some lower bound for free from above results ?
• In particular, can we say that “Assuming ETH, the prarameterised $k$-Vertex Cover problem cannot be solved in $2^{o(k)}\cdot n^{O(1)}$ time on graphs with $n$ vertices”
• Yes, because any graph with $n$ vertices has vertex cover of size $\le (n-1)$. So, $k\le n-1$