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 total computable function f : Σ* → Γ* that has the property that
- <math>
w\in A \Leftrightarrow f(w)\in B\qquad\mbox{for every } w\in\Sigma^*.
<math> If such a function f exists, we say that "A is many-one reducible to B".
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 a problem is in C by reducing a problem in C to it. Many-one reductions are valuable because most well-studied 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.
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 reduction for details.