Polynomial-time many-one reduction
= Polynomial-time many-one reduction
{wiki=Polynomial-time_reduction}
A polynomial-time many-one reduction from a <decision problem> $A$ to a decision problem $B$ is a polynomial-time computable function $r$ satisfying $x\in A$ exactly when $r(x)\in B$.