Polynomial-time reduction

Summary

A polynomial-time reduction turns instances of one decision problem into instances of another, with the same answers, by an algorithm that runs in polynomial time. It is the many-one reduction of computability theory with an added bound on running time. If a problem $A$ reduces to a problem $B$ and $B$ is in P, then $A$ is in P as well. These reductions are the tool for comparing the difficulty of problems in NP, and they define NP-hardness and NP-completeness.