In
computability theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since e ...
and
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...
, 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 whethe ...
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 reduction
In computability theory, a Turing reduction from a decision problem A to a decision problem B is an oracle machine which decides problem A given an oracle for B (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to s ...
s.
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
Emil Leon Post (; February 11, 1897 – April 21, 1954) was an American mathematician and logician. He is best known for his work in the field that eventually became known as computability theory.
Life
Post was born in Augustów, Suwałki Govern ...
in a paper published in 1944. Later
Norman Shapiro
Norman Zalmon Shapiro was an American mathematician, who was the co-author of the Rice–Shapiro theorem.
Education
Shapiro obtained a BS in Mathematics at University of Illinois in 1952.
Shapiro spent the summer of 1954 at Bell Laboratories in ...
used the same concept in 1956 under the name ''strong reducibility''.
[Norman Shapiro,]
Degrees of Computability
, Transactions of the American Mathematical Society
The ''Transactions of the American Mathematical Society'' is a monthly peer-reviewed scientific journal of mathematics published by the American Mathematical Society. It was established in 1900. As a requirement, all articles must be more than 15 p ...
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 symb ...
s over the
alphabets
An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a syllab ...
and
, respectively. A many-one reduction from
to
is a
total computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do ...
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
In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositiv ...
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
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do ...
with
If additionally
is
injective
In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositiv ...
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
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 bicon ...
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
In 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 pointers into the input, along with a logari ...
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 Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
''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
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is po ...
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
In computational complexity theory, co-NP is a complexity class. A decision problem X is a member of co-NP if and only if its complement is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP precisely ...
,
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.
Formal definition
If we denote by SPACE(''t''(''n'')), the set of all problems that can b ...
,
EXP Exp may stand for:
* Exponential function, in mathematics
* Expiry date of organic compounds like food or medicines
* Experience points, in role-playing games
* EXPTIME, a complexity class in computing
* Ford EXP, a car manufactured in the 1980s
* ...
, 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
relation
Relation or relations may refer to:
General uses
*International relations, the study of interconnection of politics, economics, and law on a global level
*Interpersonal relationship, association or acquaintance between two or more people
*Public ...
s of many-one reducibility and 1-reducibility are
transitive and
reflexive and thus induce a
preorder
In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special c ...
on the
powerset
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is postu ...
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 bicondi ...
* A set is many-one reducible to the
halting problem
In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a g ...
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 bicondi ...
it is
recursively enumerable
In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if:
*There is an algorithm such that the ...
. 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
In computer science, a universal Turing machine (UTM) is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input. The universal machine essentially achieves this by reading both the description of the machine to be simu ...
. 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
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
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 whethe ...
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
Richard Manning Karp (born January 3, 1935) is an American computer scientist and computational theorist at the University of California, Berkeley. He is most notable for his research in the theory of algorithms, for which he received a Turing A ...
. A reduction of this type is denoted by
or
.
[
]
References
{{reflist
Reduction (complexity)