Polynomial-Time Reductions
← Back to Reductions
A technique for transforming one problem into another in polynomial time. If problem A reduces to problem B, then B is at least as hard as A. This is the primary tool for proving NP-completeness.
Key Properties
Related
- NP-Complete (proved via reductions)
- Problem Transformations (the mechanics of reduction)