Reduction

/rɪˈdʌk.ʃən/ · Noun · Development · Origin: 1944

Definitions

  1. A transformation of one problem into another that preserves the difficulty relationship. If problem A reduces to problem B, then B is at least as hard as A. Polynomial-time reductions are the standard tool for proving NP-completeness.

    In plain English: Showing that one problem is at least as hard as another by converting it. If you can solve the new problem, you can solve the original one too.

    Example: "We proved our scheduling problem is NP-hard by reducing 3-SAT to it in polynomial time."

Related Terms