Given a decision problem $P$, the usual way to show that it is NP-hard is to find a known NP-hard problem $Q$, and show a polynomial-time algorithm that transforms every instance $I_Q$ of $Q$ to an instance $I_P$ of $P$, such that the answer to $I_P$ equals the answer to $I_Q$.

Consider the following, stronger kind of reduction. For every instance $I_Q$ of $Q$, we construct in polynomial time a large set $S_P$ of instances of $P$, such that the answer to any instance in $S_P$ equals the answer to $I_Q$.

Why do I think it is interesting? -- Because it shows that the problem $P$ is computationally hard, not only in some knife-edge cases, but in a substantial number of instances.

In a sense, this is the converse of Smoothed analysis: the latter aims to show that a problem is computationally tractable in a substantial number of cases.

Is this notion of "multi-reduction" known in the literature?

  • 2
    $\begingroup$ This holds automatically whenever Q has an injective reduction to P, and Q is paddable (common NP-complete problems are paddable, and assuming the Berman–Hartmanis conjecture, all NP-complete problems are). $\endgroup$ May 12 at 7:22


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.