3 ms·
I don't think your first statement is true, there exist polynomial time approximation schemes and approximation algorithms for np complete problems, notably a P
by joshuamorton 9y ago
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 9y agoThe 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.