| The reason for this apparent discrepancy is found in the difference between strong and weak NP-completeness. The fully polynomial-time approximation scheme (FPTAS) for the knapsack problem only runs in so-called pseudo-polynomial time: https://en.wikipedia.org/wiki/Pseudo-polynomial_time This means that the runtime is polynomial in the numeric value of the knapsack. Since the encoding of that numeric value only takes logarithmic space (unless you are using unary encoding), the runtime is in fact again exponential in the size of the input. For this reason, the knapsack problem is called weakly NP-complete: https://en.wikipedia.org/wiki/Weak_NP-completeness One can show that, unless P=NP, a so-called strongly NP-hard optimization problem with polynomially bounded objective function cannot have a fully polynomial-time approximation scheme: https://en.wikipedia.org/wiki/Polynomial-time_approximation_... SAT, Hamiltonian circuit etc. are strongly NP-complete: https://en.wikipedia.org/wiki/Strong_NP-completeness Thus, an FPTAS for these problems would indeed imply P=NP. |