of natural numbers, is it possible to effectively convert a method for deciding membership in
This gives a powerful technique for proving that many sets are noncomputable.
A reducibility relation is a binary relation on sets of natural numbers that is These two properties imply that 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
if and only if any (possibly noneffective) decision procedure for
can be effectively converted to a decision procedure for
The different reducibility relations vary in the methods they permit such a conversion process to use.
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.
It is common, as shown here, to use boldface notation to denote degrees.
of natural numbers is Turing reducible to a set
if and only if there is an oracle Turing machine that, when run with
if and only if there is an algorithm for computing the indicator function for
provided that the algorithm is provided with a means to correctly answer questions of the form "Is
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.
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.
The strong reducibilities include Many of these were introduced by Post (1944).
Post was searching for a non-computable, computably 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.
A bounded form of each of the above strong reducibilities can be defined.
These first three are the most common ones and they are based on the number of queries.
on these numbers and then terminates for all possible oracle answers; the value
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.
under any of the strong reducibility relations listed above, even if
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.
Other resource-bounded reducibilities are used in other contexts of computational complexity theory where other resource bounds are of interest.
These reducibilities are related to the relative definability of sets over arithmetic or set theory.