2 ms·
Some NP-complete problems have provably bad approximations if P!=NP. You don't get the same polynomial reduction behavior if you are using approximation algorit
by UncleMeat 6y ago
Some NP-complete problems have provably bad approximations if P!=NP. You don't get the same polynomial reduction behavior if you are using approximation algorithms. So for some problems we may have utterly practical algorithms and for others we never will (assuming P!=NP).