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.

Principle

The key rule is preservation of membership by a single effectively calculable transformation: a computable f provides a uniform, instancewise translation from A-instances to B-instances so that solving B on f(x) solves A on x without further queries or adaptation.

Demonstration

The classic example is reducing the halting set of machines with input encodings to a tailored language: produce f that transforms an instance encoding of machine M and input w into an encoding of a machine M' that halts trivially iff M halts on w; membership is preserved by computable transformation.

Misapplication

Confusing many-one reducibility with Turing reducibility and therefore permitting adaptive or multiple oracle queries, or using noncomputable transformations and still claiming many-one reducibility.

Consequence

When A ≤_m B holds, any decision procedure for B yields a decision procedure for A by composing with f; many-one reducibility yields partial orderings of degrees of difficulty and supports completeness notions (m-completeness) under effective translations.

Reversal

Reversing to B reducible to A (B ≤_m A) changes the direction of hardness: if both directions hold the problems are m-equivalent, but if only reversed direction holds one cannot transfer algorithms from A to B via a single computable mapping.

Boundary

Applies to sets or languages and to computable functions as translators; it excludes randomized, approximate, or nonuniform reductions, and does not account for reductions that use additional queries to an oracle or resource-bounded computations unless specified.

Semantic Tension

Many-one reducibility is close to one-one reducibility and truth-table reducibility: one-one requires injective translators, truth-table allows nonadaptive parallel queries; the distinctions affect degree structure and completeness criteria.

Synthesis

Many-one reducibility is the nonadaptive, single-transformation notion of relative computability: a computable function uniformly translates instances of A into instances of B so that membership is preserved, yielding a robust notion of reducibility and completeness under effective mappings.