On: Evidence of exponential speed-up in the solution o...

[joshuamorton]

I don't think your first statement is true, there exist polynomial time approximation schemes and approximation algorithms for np complete problems, notably a PTAS for knapsack. In other words, an approximation of one np complete problems doesn't imply an approximation of all of them.

I can't fully articulate the reasons for this though.

[zmonx → joshuamorton]

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.