66 Lower Bounds Based on the Exponential Time Hypothesis (ETH)

Big-O

$f(n)=O(g(n))$ if $\exists$ constant $M\ge 0$ and $n_0\in \mathrm{N}$ such that $\forall n\ge n_0$ we have $f(n)\le M\cdot g(n)$

Little-O

$f(n)=O(g(n))$ if ${\lim }_{n\to \infty }\frac{f(n)}{g(n)}=0$

What is the status of showing lower bounds ?

• We (mostly) believe $\mathrm{P}\ne \mathrm{NP}$
• Hence, we do not expect polynomial time algorithm for $\mathrm{NP}$ hard problems algorithms

Example

Given an undirected graph $G=(V,E)$ on $n$ vertices and $m$ edges, find a set $X$ of minimum size such that each edge of $G$ has at least one-endpoint in $X$.

• Brute force algorithm runs in $2^n\cdot n^{O(1)}$ time
• We designed an $1.47^n\cdot n^{O(1)}$ time algorithm via branching