Reductions

Reductions are a term used in several fields, but they share a common idea: transforming one object into another in a way that preserves essential structure or information. In mathematics and computer science, a reduction is a method for converting one problem into another so that a solution to the second problem can be turned back into a solution for the first. This concept is central to analyzing algorithmic difficulty, proving hardness results, and transferring techniques between problems.

In computational complexity theory, reductions are formal ways to relate problems. A many-one (Karp) reduction maps instances of problem A to instances of problem B via a computable function, such that the answer to A is yes if and only if the mapped instance is a yes for B. If the mapping can be computed in polynomial time, it is a polynomial-time reduction. Such reductions are used to define hardness and completeness; for example, a problem is NP-complete if it is in NP and every NP problem reduces to it by a polynomial-time many-one reduction.

Another type is a Turing (Cook) reduction, which allows an algorithm solving A to make queries to a subroutine that solves B. This captures a broader notion of hardness, since A can be solved using an oracle for B.

In chemistry, reductions refer to redox reactions in which a substance gains electrons and becomes reduced, decreasing its oxidation state. The opposite process, oxidation, involves electron loss. Reducing agents donate electrons to other species.

Beyond these, reductions appear in various disciplines as methods for simplification or reformulation, preserving essential properties while enabling easier analysis or computation.