Many-One Reducibility

- Natural & Formal Sciences -
Mathematics & Logic Dictionary
A computability relation between decision problems A and B: A is many-one reducible to B if there exists a computable function f mapping instances x to f(x) such that x is in A exactly when f(x) is in B. The reduction is single-call and nonadaptive.