Skip to main content
1 of 1
Michael
  • 2.2k
  • 34
  • 42

Approximation-preserving reductions between optimization problems in the same complexity class.

This may require a bit of explanation. My trade is developing polynomial approximation algorithms for various computational problems that are known to be NP-hard. Most of these problems polynomially reduce to each other; if the reductions could be extended to the corresponding approximation algorithms I (as well as numerous other mathematicians and software engineers) would be out of business.

However, one of the consequences of PCP theorem is that, provided that $NP\neq P$, the existence of a polynomial reduction between problems does not imply the existence of a polynomial reduction between the corresponding approximation problems.

Michael
  • 2.2k
  • 34
  • 42