Home > Many-one reduction
In computational complexity theory, a many-one reduction is a reduction which converts instances of a decision problem problem A into instances of a decision problem B. We write A ≤m B or "A is many-one reducible to B". If we have an algorithm N which solves instances of B, we can use it to solve instances of A in:- the time needed for N plus the time needed for the reduction;
- the maximum of the space needed for N and the space needed for the reduction.
More formally, suppose A and B are formal languages over the alphabets Σ and Γ, respectively. A many-one reduction from A to B is a function f : Σ* → Γ* that has the property that
-
If such a function f exists, we say that "L is many-one reducible to M".
We say that a class C of languages is closed under many-one reducibility if there exists no reduction from a language in C to a language outside C. If a class is closed under many-one reducibility, then many-one reduction can be used to show that is in C by reducing a problem in C to it. Many-one reductions are valuable because most complexity classes are closed under some type of many-one reducibility, including P, NP, L, NL, co-NP, PSPACE, EXP, and many others.
Many-one reductions are a special case and a weaker form of Turing reductions where only one invocation of the oracle is allowed, and only at the end. Turing reductions are sometimes more convenient for designing reduction algorithms, but their power also causes several important classes such as NP to not be closed under Turing reductions, meaning that many-one reductions must be used to show that a problem is in the class.
Many-one reductions are often subjected to additional resource restrictions, for example that the function is computable in polynomial time or logarithmic space; see see polynomial-time reduction and log-space reductionIn computational complexity theory, a log-space reduction is a reduction computable by a deterministic Turing machine using logarithmic space. Conceptually, this means it can keep a constant number of points into the input, along with a logarithmic number for details.
Computational complexity theory
