In
computability theory and
computational complexity theory, a many-one reduction (also called mapping reduction
) is a
reduction which converts instances of one
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whe ...
into instances of a second decision problem
where the instance reduced to is in the language
if the initial instance was in its language
and is not in the language
if the initial instance was not in its language
. Thus if we can decide whether
instances are in the language
, we can decide whether
instances are in its language by applying the reduction and solving
. Thus, reductions can be used to measure the relative computational difficulty of two problems. It is said that
reduces to
if, in layman's terms
is harder to solve than
. That is to say, any algorithm that solves
can also be used as part of a (otherwise relatively simple) program that solves
.
Many-one reductions are a special case and stronger form of
Turing reductions.
With many-one reductions, the oracle (that is, our solution for B) can be invoked only once at the end, and the answer cannot be modified. This means that if we want to show that problem A can be reduced to problem B, we can use our solution for B only once in our solution for A, unlike in Turing reduction, where we can use our solution for B as many times as needed while solving A.
This means that many-one reductions map instances of one problem to instances of another, while Turing reductions compute the solution to one problem, assuming the other problem is easy to solve. The many-one reduction is more effective at separating problems into distinct complexity classes. However, the increased restrictions on many-one reductions make them more difficult to find.
Many-one reductions were first used by
Emil Post in a paper published in 1944. Later
Norman Shapiro used the same concept in 1956 under the name ''strong reducibility''.
[Norman Shapiro,]
Degrees of Computability
, Transactions of the American Mathematical Society 82, (1956) 281–299
Definitions
Formal languages
Suppose
and
are
formal language
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of sym ...
s over the
alphabets and
, respectively. A many-one reduction from
to
is a
total computable function that has the property that each word
is in
if and only if
is in
.
If such a function
exists, we say that
is many-one reducible or m-reducible to
and write
:
If there is an
injective many-one reduction function then we say ''A'' is 1-reducible or one-one reducible to
and write
:
Subsets of natural numbers
Given two sets
we say
is many-one reducible to
and write
:
if there exists a
total computable function with
If additionally
is
injective we say
is 1-reducible to
and write
:
Many-one equivalence and 1-equivalence
If
we say
is many-one equivalent or m-equivalent to
and write
:
If
we say
is 1-equivalent to
and write
:
Many-one completeness (m-completeness)
A set
is called ''many-one complete'', or simply m-complete,
iff is recursively enumerable and every recursively enumerable set
is m-reducible to
.
Many-one reductions with resource limitations
Many-one reductions are often subjected to resource restrictions, for example that the reduction function is computable in polynomial time, logarithmic space, by
or
circuits, or polylogarithmic projections where each subsequent reduction notion is weaker than the prior; see
polynomial-time reduction
In computational complexity theory, a polynomial-time reduction is a method for solving one problem using another. One shows that if a hypothetical subroutine solving the second problem exists, then the first problem can be solved by transforming ...
and
log-space reduction for details.
Given decision problems
and
and an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
''N'' which solves instances of
, we can use a many-one reduction from
to
to solve instances of
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
We say that a class C of languages (or a subset of the
power set of the natural numbers) 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. It is known for example that the first four listed are closed up to the very weak reduction notion of polylogarithmic time projections. These classes are not closed under arbitrary many-one reductions, however.
Properties
* The
relations of many-one reducibility and 1-reducibility are
transitive and
reflexive and thus induce a
preorder on the
powerset of the natural numbers.
*
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bic ...
* A set is many-one reducible to the
halting problem if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bic ...
it is
recursively enumerable. This says that with regards to many-one reducibility, the halting problem is the most complicated of all recursively enumerable problems. Thus the halting problem is r.e. complete. Note that it is not the only r.e. complete problem.
* The specialized halting problem for an ''individual'' Turing machine ''T'' (i.e., the set of inputs for which ''T'' eventually halts) is many-one complete iff ''T'' is a
universal Turing machine. Emil Post showed that there exist recursively enumerable sets that are neither
decidable nor m-complete, and hence that ''there exist
nonuniversal Turing machines whose individual halting problems are nevertheless undecidable''.
Karp reductions
A
polynomial-time many-one reduction from a problem ''A'' to a problem ''B'' (both of which are usually required to be
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whe ...
s) is a polynomial-time algorithm for transforming inputs to problem ''A'' into inputs to problem ''B'', such that the transformed problem has the same output as the original problem. An instance ''x'' of problem ''A'' can be solved by applying this transformation to produce an instance ''y'' of problem ''B'', giving ''y'' as the input to an algorithm for problem ''B'', and returning its output. Polynomial-time many-one reductions may also be known as polynomial transformations or Karp reductions, named after
Richard Karp. A reduction of this type is denoted by
or
.
[
]
References
{{reflist
Reduction (complexity)