Reduction (computability theory)

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.

Reducibility relations

A decision procedure for a set A of natural numbers is a function that, given a natural number n returns 1 if n is in A and returns 0 otherwise. In other words, a decision procedure computes (in some sense) the indicator function of a set. The decision procedure is not identified with the function it computes, but is viewed as a black box that performs some "procedure" (which may not be effective) in order to produce each output.

A reducibility relation is a binary relation on sets of natural numbers that is

Reflexive: Every set is reducible to itself.
Transitive: 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 on the powerset of the natural numbers. Not all preorders are studied as reducibility notions, however. The notions studied in computability theory have the property that A is reducible to B if and only if a decision procedure for A can be effectively converted to a decision procedure for B. 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 classess 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 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 reducibility: A is one-one reducible to B iff there is a computable one-one function f with A(x) = B(f(x)) for all x.

Many-one reducibility: the same as one-one without the constraint of one-one-ness on f.

Truth-table reducible: A is truth-table reducible to B iff A is Turing reducible to B via a Turing machine which produces a total function relative to every oracle.
Weak truth-table reducible: A is Turing reducible to B via a Turing machine M such that there exists a recursive function f so that M on input x never queries B at any y > f(x). One can show that A is truth-table reducible to B iff there are computable functions f and g such that A(x) = g(x,B(0),B(1),...,B(f(x))), hence whenever A is truth-table reducible to B then A is also weak truth-table reducible to B.
Positive reducible: A is positive reducible to B iff 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 iff a computable function computes for each x a finite set F(x) given as an explicit list of numbers such that x ∈ A iff F(x) contains an odd number of elements of B.

Many of these were introduced by Post (1944). They 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 iff 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 is is not reasonable for computational complexity theory, 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 reducibilites are used in other contexts of omputational complexity theory where other resource bounds are of interest.

Reductions weaker than Turing reducibility

Although Turing reducibility is the most general effective reducibility, there are reducibility relations weaker than this that are commonly studied. These notions emphasize the 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 theorem, A is arithemtical in B if and only if A is Turing reducible to $B^{(n)}$ , the nth Turing jump of B, for some natural number n. The arithmetical hierarchy gives a finer classification of arithmetical reducibility.
Hyperarithmetical reducibility: A set A is hyperarithmetical in a set B if A is $\Delta _{1}^{1}$ definable (see analytical hierarchy) over the standard model of Peano arithmetic with a predicate for B. Equivalently, A is hyperarithemtical in B if and only if A is Turing reducible to $B^{(\alpha )}$ , the αth Turing jump of B, for some recursive ordinal α.
Relative constructibility: A set A is constructible from a set B if A is in L[B], the smallest model of ZFC set theory containing B and all the ordinals.

References

K. Ambos-Spies and P. Fejer, 2006. "Degrees of Unsolvability." Unpublished preprint.
P. Odifreddi, 1989. Classical Recursion Theory, North-Holland. ISBN 0-444-87295-7
P. Odifreddi, 1999. Classical Recursion Theory, Volume II, Elsevier. ISBN 0-444-50205-X
E. Post, 1944, "Recursively enumerable sets of positive integers and their decision problems", Bulletin of the American Mathematical Society, volume 50, pages 284–316.
H. Rogers, Jr., 1967. The Theory of Recursive Functions and Effective Computability, second edition 1987, MIT Press. ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1
G Sacks, 1990. Higher Recursion Theory, Springer-Verlag. ISBN 3-540-19305-7