Reduction (recursion theory)
Encyclopedia
In computability theory
, many reducibility relations (also called reductions, reducibilities, and notions of reducibility) are studied. They are motivated by the question: given sets A and B of natural numbers, is it possible to effectively convert a method for deciding membership in B into a method for deciding membership in A? If the answer to this question is affirmative then A is said to be reducible to B.
The study of reducibility notions is motivated by the study of decision problems. For many notions of reducibility, if any noncomputable set is reducible to a set A then A must also be noncomputable. This gives a powerful technique for proving that many sets are noncomputable.
These two properties imply that a reducibility is a preorder
on the powerset of the natural numbers. Not all preorders are studied as reducibility notions, however. The notions studied in computability theory have the informal property that A is reducible to B if and only if any (possibly noneffective) decision procedure for B can be effectively converted to a decision procedure for A. The different reducibility relations vary in the methods they permit such a conversion process to use.
The degrees of any reducibility relation are partially ordered by the relation in the following manner. Let ≤ be a reducibility relation and let A and B be two of its degrees. Then A ≤ B if and only if there is a set A in A and a set B in B such that A ≤ B. This is equivalent to the property that for every set A in A and every set B in B, A ≤ B, because any two sets in A are equivalent and any two sets in B are equivalent. It is common, as shown here, to use boldface notation to denote degrees.
Turing reducibility serves as a dividing line for other reducibility notions because, according to the Church-Turing thesis, it is the most general reducibility relation that is effective. Reducibility relations that imply Turing reducibility have come to be known as strong reducibilities, while those that are implied by Turing reducibility are weak reducibilities. Equivalently, a strong reducibility relation is one whose degrees form a finer equivalence relation than the Turing degrees, while a weak reducibility relation is one whose degrees form a coarser equivalence relation than Turing equivalence.
Many of these were introduced by Post (1944). Post was searching for a non-recursive
, recursively enumerable set which the halting problem
could not be Turing reduced to. As he could not construct such a set in 1944, he instead worked on the analogous problems for the various reducibilities that he introduced. These reducibilities have since been the subject of much research, and many relationships between them are known.
, which studies which sets can be decided under certain asymptotical resource bounds.
The most common reducibility in computational complexity theory is polynomial-time reducibility
; a set A is polynomial-time reducible to a set B if there is a polynomial-time function f such that for every n, n is in A if and only if f(n) is in B. This reducibility is, essentially, a resource-bounded version of many-one reducibility. Other resource-bounded reducibilities are used in other contexts of computational complexity theory where other resource bounds are of interest.
Computability theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
, many reducibility relations (also called reductions, reducibilities, and notions of reducibility) are studied. They are motivated by the question: given sets A and B of natural numbers, is it possible to effectively convert a method for deciding membership in B into a method for deciding membership in A? If the answer to this question is affirmative then A is said to be reducible to B.
The study of reducibility notions is motivated by the study of decision problems. For many notions of reducibility, if any noncomputable set is reducible to a set A then A must also be noncomputable. This gives a powerful technique for proving that many sets are noncomputable.
Reducibility relations
A reducibility relation is a binary relation on sets of natural numbers that is- ReflexiveReflexive relationIn mathematics, a reflexive relation is a binary relation on a set for which every element is related to itself, i.e., a relation ~ on S where x~x holds true for every x in S. For example, ~ could be "is equal to".-Related terms:...
: Every set is reducible to itself. - TransitiveTransitive relationIn mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....
: If a set A is reducible to a set B and B is reducible to a set C then A is reducible to C.
These two properties imply that a reducibility is a preorder
Preorder
In mathematics, especially in order theory, preorders are binary relations that are reflexive and transitive.For example, all partial orders and equivalence relations are preorders...
on the powerset of the natural numbers. Not all preorders are studied as reducibility notions, however. The notions studied in computability theory have the informal property that A is reducible to B if and only if any (possibly noneffective) decision procedure for B can be effectively converted to a decision procedure for A. The different reducibility relations vary in the methods they permit such a conversion process to use.
Degrees of a reducibility relation
Every reducibility relation (in fact, every preorder) induces an equivalence relation on the powerset of the natural numbers in which two sets are equivalent if and only if each one is reducible to the other. In recursion theory, these equivalence classes are called the degrees of the reducibility relation. For example, the Turing degrees are the equivalence classes of sets of naturals induced by Turing reducibility.The degrees of any reducibility relation are partially ordered by the relation in the following manner. Let ≤ be a reducibility relation and let A and B be two of its degrees. Then A ≤ B if and only if there is a set A in A and a set B in B such that A ≤ B. This is equivalent to the property that for every set A in A and every set B in B, A ≤ B, because any two sets in A are equivalent and any two sets in B are equivalent. It is common, as shown here, to use boldface notation to denote degrees.
Turing reducibility
The most fundamental reducibility notion is Turing reducibility. A set A of natural numbers is Turing reducible to a set B if and only if there is an oracle Turing machine that, when run with B as its oracle set, will compute the indicator function (characteristic function) of A. Equivalently, A is Turing reducible to B if and only if there is an algorithm for computing the indicator function for A provided that the algorithm is provided with a means to correctly answer questions of the form "Is n in B?".Turing reducibility serves as a dividing line for other reducibility notions because, according to the Church-Turing thesis, it is the most general reducibility relation that is effective. Reducibility relations that imply Turing reducibility have come to be known as strong reducibilities, while those that are implied by Turing reducibility are weak reducibilities. Equivalently, a strong reducibility relation is one whose degrees form a finer equivalence relation than the Turing degrees, while a weak reducibility relation is one whose degrees form a coarser equivalence relation than Turing equivalence.
Reductions stronger than Turing reducibility
The strong reducibilities include- One-one reducibilityMany-one reductionIn computability theory and computational complexity theory, a many-one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem. Reductions are thus used to measure the relative computational difficulty of two problems.Many-one...
: A is one-one reducible to B if there is a computable one-to-one functionInjective functionIn mathematics, an injective function is a function that preserves distinctness: it never maps distinct elements of its domain to the same element of its codomain. In other words, every element of the function's codomain is mapped to by at most one element of its domain...
f with A(x) = B(f(x)) for all x. - Many-one reducibilityMany-one reductionIn computability theory and computational complexity theory, a many-one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem. Reductions are thus used to measure the relative computational difficulty of two problems.Many-one...
: A is many-one reducible to B if there is a computable function f with A(x) = B(f(x)) for all x. - Truth-table reducibleTruth table reductionIn computability theory, a truth-table reduction is a reduction from one set of natural numbers to another.As a "tool", it is weaker than Turing reduction, since not every Turing reduction between sets can be performed by a truth-table reduction, but every truth-table reduction can be performed by...
: A is truth-table reducible to B if A is Turing reducible to B via a single (oracle) Turing machine which produces a total function relative to every oracle. - Weak truth-table reducibleTruth table reductionIn computability theory, a truth-table reduction is a reduction from one set of natural numbers to another.As a "tool", it is weaker than Turing reduction, since not every Turing reduction between sets can be performed by a truth-table reduction, but every truth-table reduction can be performed by...
: A is weak truth-table reducible to B if there is a Turing reduction from B to A and a recursive function f which bounds the use. Whenever A is truth-table reducible to B, A is also weak truth-table reducible to B, since one can construct a recursive bound on the use by considering the maximum use over the tree of all oracles, which will exist if the reduction is total on all oracles. - Positive reducible: A is positive reducible to B if and only if A is truth-table reducible to B in a way that one can compute for every x a formula consisting of atoms of the form B(0), B(1), ... such that these atoms are combined by and's and or's, where the and of a and b is 1 if a = 1 and b = 1 and so on.
- Disjunctive reducible: Similar to positive reducible with the additional constraint that only or's are permitted.
- Conjunctive reducibility: Similar to positive reducibility with the additional constraint that only and's are permitted.
- Linear reducibility: Similar to positive reducibility but with the constraint that all atoms of the form B(n) are combined by exclusive or's. In other words, A is linear reducible to B if and only if a computable function computes for each x a finite set F(x) given as an explicit list of numbers such that x ∈ A if and only if F(x) contains an odd number of elements of B.
Many of these were introduced by Post (1944). Post was searching for a non-recursive
Recursive set
In computability theory, a set of natural numbers is called recursive, computable or decidable if there is an algorithm which terminates after a finite amount of time and correctly decides whether or not a given number belongs to the set....
, recursively enumerable set which the halting problem
Halting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
could not be Turing reduced to. As he could not construct such a set in 1944, he instead worked on the analogous problems for the various reducibilities that he introduced. These reducibilities have since been the subject of much research, and many relationships between them are known.
Bounded reducibilities
A bounded form of each of the above strong reducibilities can be defined. The most famous of these is bounded truth-table reduction, but there are also bounded Turing, bounded weak truth-table and others. These first three are the most common ones and they are based on the number of queries. For example, a set A is bounded truth-table reducible to B if and only if the Turing machine M computing A relative to B computes a list of up to n numbers, queries B on these numbers and then terminates for all possible oracle answers; the value n is a constant independent of x. The difference between bounded weak truth-table and bounded Turing reduction is that in the first case, the up to n queries have to be made at the same time while in the second case, the queries can be made one after the other. For that reason, there are cases where A is bounded Turing reducible to B but not weak truth-table reducible to B.Strong reductions in computational complexity
The strong reductions listed above restrict the manner in which oracle information can be accessed by a decision procedure but do not otherwise limit the computational resources available. Thus if a set A is decidable then A is reducible to any set B under any of the strong reducibility relations listed above, even if A is not polynomial-time or exponential-time decidable. This is acceptable in the study of recursion theory, which is interested in theoretical computability, but it is not reasonable for computational complexity theoryComputational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, which studies which sets can be decided under certain asymptotical resource bounds.
The most common reducibility in computational complexity theory is polynomial-time reducibility
Polynomial-time reduction
In computational complexity theory a polynomial-time reduction is a reduction which is computable by a deterministic Turing machine in polynomial time. If it is a many-one reduction, it is called a polynomial-time many-one reduction, polynomial transformation, or Karp reduction...
; a set A is polynomial-time reducible to a set B if there is a polynomial-time function f such that for every n, n is in A if and only if f(n) is in B. This reducibility is, essentially, a resource-bounded version of many-one reducibility. Other resource-bounded reducibilities are used in other contexts of computational complexity theory where other resource bounds are of interest.
Reductions weaker than Turing reducibility
Although Turing reducibility is the most general reducibility that is effective, weaker reducibility relations are commonly studied. These reducibilities are related to relative definability of sets over arithmetic or set theory. They include:- Arithmetical reducibility: A set A is arithmetical in a set B if A is definable over the standard model of Peano arithmetic with an extra predicate for B. Equivalently, according to Post's theoremPost's theoremIn computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees.- Background :The statement of Post's theorem uses several concepts relating to definability and recursion theory...
, A is arithmetical in B if and only if A is Turing reducible to
, the nth Turing jumpTuring jumpIn computability theory, the Turing jump or Turing jump operator, named for Alan Turing, is an operation that assigns to each decision problem a successively harder decision problem with the property that is not decidable by an oracle machine with an oracle for .The operator is called a jump...
of B, for some natural number n. The arithmetical hierarchyArithmetical hierarchyIn mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene-Mostowski hierarchy classifies certain sets based on the complexity of formulas that define them...
gives a finer classification of arithmetical reducibility. - Hyperarithmetical reducibility: A set A is hyperarithmetical in a set B if A is
definable (see analytical hierarchyAnalytical hierarchyIn mathematical logic and descriptive set theory, the analytical hierarchy is a higher type analogue of the arithmetical hierarchy. It thus continues the classification of sets by the formulas that define them.-The analytical hierarchy of formulas:...
) over the standard model of Peano arithmetic with a predicate for B. Equivalently, A is hyperarithmetical in B if and only if A is Turing reducible to
, the αth Turing jumpTuring jumpIn computability theory, the Turing jump or Turing jump operator, named for Alan Turing, is an operation that assigns to each decision problem a successively harder decision problem with the property that is not decidable by an oracle machine with an oracle for .The operator is called a jump...
of B, for some B-recursive ordinalRecursive ordinalIn mathematics, specifically set theory, an ordinal \alpha is said to be recursive if there is a recursive binary relation R that well-orders a subset of the natural numbers and the order type of that ordering is \alpha....
α. - Relative constructibility: A set A is relatively constructible from a set B if A is in L(B), the smallest transitive model of ZFC set theory containing B and all the ordinals.