The reason for this apparent discrepancy is found in the difference between strong and weak NP-completeness. The fully polynomial-time approximation scheme (FP

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 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 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_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 https://en.wikipedia.org/wiki/Strong_NP-completeness Thus, an FPTAS for these problems would indeed imply P=NP.