Réduction Many-One

Une relation de calculabilité entre problèmes de décision A et B : A est réductible many-one à B s'il existe une fonction calculable f transformant des instances x en f(x) telle que x appartient à A exactement lorsque f(x) appartient à B. La réduction est à appel unique et non adaptative.