A systematic transformation that maps instances and solutions of a problem or structure in one domain to instances and solutions in another domain so that solvability or essential properties are preserved or reflected.

Principle

A reduction provides a rule or construction R and a reconstruction or interpretation S such that solving R(x) in the target domain yields, via S, a solution to x in the source domain; reductions order problems by relative difficulty or expressiveness.

Demonstration

In computability theory, a many-one reduction f maps instances x of language A to instances f(x) of language B so that x∈A if and only if f(x)∈B; thus decidability of B implies decidability of A by composing a decider for B with f.

Misapplication

Treating any mapping between problems as a reduction without verifying preservation of solution existence or correctness—for example using an injective encoding that does not allow reconstruction of a valid source solution.

Consequence

A correct reduction transfers known results: hardness, decidability/undecidability, or complexity upper bounds flow from the target to the source according to the reduction’s constraints (e.g., polynomial-time reductions preserve polynomial-time membership implications).

Reversal

The inverse relation, when it exists, is a reduction in the opposite direction; absence of a reverse reduction indicates an asymmetry in difficulty or expressiveness between domains.

Boundary

Reductions require a precise specification of allowed resources and transformations (type: many-one, Turing, polynomial-time, parsimonious, etc.); mappings that change the problem’s acceptance criterion or rely on nonconstructive steps fall outside the scope.

Semantic Tension

Reduction vs. equivalence: a reduction shows relative transformability but not necessarily two-way equivalence; reductions are often conflated with isomorphisms or mutual encodings when bidirectionality is not proved.

Synthesis

Reduction is a constructive bridge: a computable or constructive mapping plus a valid back-translation that relocates solvability or structural properties from one domain to another under specified resource constraints.