Many-one reduction
In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction that converts instances of one decision problem (whether an instance is in L 1 {\displaystyle L_{1}} ) to another decision problem (whether an instance is in L 2 {\displaystyle L_{2}} ) using a computable function. The reduced instance is in the language L 2 {\displaystyle L_{2}} if and only if the initial instance is in its language L 1 {\displaystyle L_{1}} .