Are there any examples of hardness-of-approximation reductions where we get a better hardness bound for the problem we've reduced to than the problem we've reduced from? In the examples I've seen so far, the bound is usually degraded in the reduction.

  • 2
    $\begingroup$ A lot of reductions amplify hardness by toying with the objective function. For example, Min Circuit SAT (given a Boolean circuit, what is the smallest hamming-weight input that evaluates to true) is NP-hard because it can encode min vertex cover. This gives a small hardness factor of ~2. So it's hard to distinguish instances that can be solved with weight a=f(n) from those with weight 1.5a. But now we can reduce from this circuit sat instance by making the circuit that accepts either solutions to the original CSAT instance of weight <= a, or anything of weight > n/2, for $\omega(1)$ hardness. $\endgroup$ – Yonatan N Jun 20 '19 at 19:01
  • $\begingroup$ @YonatanN That's a great example. I would accept it as an answer if you want to copy paste it. $\endgroup$ – Elliot Gorokhovsky Jun 23 '19 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.