# SAT to knapsack vs. ETH

Theorem states that every problem in $\mathsf{NP}$ can be reduced to another $\mathsf{NP}$-complete problem in polynomial time. Also you can only make a problem polynomially longer using polynomial time.

Thus SAT of length $n$ can be reduced to knapsack with length $n^k$ for some fixed $k\in\mathbb{R}^+$. We don't need to show that reduction, we only need to know that it exists.

Knapsack has quasipolynomial algorithm, in other words running time is $O(\alpha^{\log^p q})$ where $\{p,\alpha\}\in\mathbb{R}^+$ are some fixed numbers and $q$ is length of knapsack problem.

Now assuming we have converted SAT to knapsack we get runtime $O(\alpha^{\log^p n^k})=O(\alpha^{k^p\log^p n})=O(\beta^{\log^p n})$ where $\beta\in\mathbb{R}^+$ is some fixed number. So, the runtime is quasipolynomial.

Why doesn't this simply negate ETH?

Knapsack does not have any known quasipolynomial time algorithm (one which runs in $n^{poly(\log n)}$ time, with $n$ being the inputs length).
What it does have is a pseudo-polynomial time algorithm, i.e. an algorithm which requires polynomial time in the numeric value of the input, but exponential in the length of its description. The dynamic programming algorithm for knapsack runs in time $O(nW)$, however the input $W$ when given in binary representation requires $\log W$ bits, so the algorithm is actually exponential (and not quasipolynomial).
• In fact no NP-complete problem has $o(exp)$ algorithm? $exp$ can be $2^{\sqrt n}$, of course. Aug 18, 2017 at 15:59