1
$\begingroup$

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?

|cite|improve this question
$\endgroup$
3
$\begingroup$

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).

|cite|improve this answer
$\endgroup$
  • $\begingroup$ In fact no NP-complete problem has $o(exp)$ algorithm? $exp$ can be $2^{\sqrt n}$, of course. $\endgroup$ – rus9384 Aug 18 '17 at 15:59
  • $\begingroup$ If the exponential time hypothesis holds then the answer is no. $\endgroup$ – Ariel Aug 18 '17 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.