In computability theory, many reducibility relations (also called reductions, reducibilities, and notions of reducibility of natural numbers, is it possible to effectively is said to be reducible to.

The study of reducibility notions is motivated by the study of decision problems. For many notions of reducibility, if any noncomputable 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

• Reflexive: Every set is reducible to itself.

• Transitive.

These two properties imply that reducibility is a preorder if and only if. 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 computability 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, because any two sets in C 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 of natural numbers is Turing reducible if and only if there is an oracle Turing machine as its oracle set, will compute the indicator function?".

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 if there is a computable one-to-one function.

• Many-one reducibility.

• Truth-table reducible via a single (oracle) Turing machine that produces a total function relative to every oracle.

• Weak truth-table reducible that bounds the use, since one can construct a computable 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.

• and so on.

• Enumeration reducibility: Similar to positive reducibility, relating to the effective procedure of enumerability.

• 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.

• are combined by exclusive or's a finite set.

Many of these were introduced by Post (1944). Post was searching for a non-computable, computably enumerable set that 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.

Bounded reducibilities

A bounded.

Strong reductions in computational complexity

is decidable under any of the strong reducibility relations listed above, is not polynomial-time or exponential-time decidable. This is acceptable in the study of computability theory, which is interested in theoretical computability, but it 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 if there is a polynomial-time function f. 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 the relative definability of sets over arithmetic or set theory. They include:

• Arithmetical reducibility is definable over the standard model of Peano arithmetic. Equivalently, according to Post's theorem, Ath Turing jump. The arithmetical hierarchy gives a finer classification of arithmetical reducibility.

• Hyperarithmetical reducibility definable (see analytical hierarchyth Turing jump-recursive ordinal.

• Relative constructibility, the smallest transitive model of ZFC set theory and all the ordinalss.

Notes

References

• K. Ambos-Spies and P. Fejer, 2006. "Degrees of Unsolvability." Unpublished preprint.

• P. Odifreddi, 1989. Classical Recursion Theory, North-Holland.

• P. Odifreddi, 1999. Classical Recursion Theory, Volume II, Elsevier.

• E. Post, 1944, "Recursively enumerable sets of positive integers and their decision problems", Bulletin of the American Mathematical Society, volume 50, pages 284316.

• H. Rogers, Jr., 1967. The Theory of Recursive Functions and Effective Computability, second edition 1987, MIT Press. (paperback),

• G. Sacks, 1990. Higher Recursion Theory, Springer-Verlag.

External links

• Stanford Encyclopedia of Philosophy: Recursive Functions