Reduction (computability theory)

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 ${\displaystyle A}$ is reducible to a set ${\displaystyle B}$ and ${\displaystyle B}$ is reducible to a set ${\displaystyle C}$ then ${\displaystyle A}$ is reducible to ${\displaystyle C}$.

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 ${\displaystyle A}$ is reducible to ${\displaystyle B}$ if and only if any (possibly noneffective) decision procedure for ${\displaystyle B}$ can be effectively converted to a decision procedure for ${\displaystyle A}$. The different reducibility relations vary in the methods they permit such a conversion process to use.

The most fundamental reducibility notion is Turing reducibility. A set ${\displaystyle A}$ of natural numbers is Turing reducible to a set ${\displaystyle B}$ if and only if there is an oracle Turing machine that, when run with ${\displaystyle B}$ as its oracle set, will compute the indicator function (characteristic function) of ${\displaystyle A}$. Equivalently, ${\displaystyle A}$ is Turing reducible to ${\displaystyle B}$ if and only if there is an algorithm for computing the indicator function for ${\displaystyle A}$ provided that the algorithm is provided with a means to correctly answer questions of the form "Is ${\displaystyle n}$ in ${\displaystyle 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.

The strong reducibilities include

• One-one reducibility: ${\displaystyle A}$ is one-one reducible to ${\displaystyle B}$ if there is a computable one-to-one function ${\displaystyle f}$ with ${\displaystyle A(x)=B(f(x))}$ for all ${\displaystyle x}$.
• Many-one reducibility: ${\displaystyle A}$ is many-one reducible to ${\displaystyle B}$ if there is a computable function ${\displaystyle f}$ with ${\displaystyle A(x)=B(f(x))}$ for all ${\displaystyle x}$.
• Truth-table reducible: ${\displaystyle A}$ is truth-table reducible to ${\displaystyle B}$ if ${\displaystyle A}$ is Turing reducible to ${\displaystyle B}$ via a single (oracle) Turing machine which produces a total function relative to every oracle.
• Weak truth-table reducible: ${\displaystyle A}$ is weak truth-table reducible to ${\displaystyle B}$ if there is a Turing reduction from ${\displaystyle B}$ to ${\displaystyle A}$ and a computable function ${\displaystyle f}$ which bounds the use. Whenever ${\displaystyle A}$ is truth-table reducible to ${\displaystyle B}$, ${\displaystyle A}$ is also weak truth-table reducible to ${\displaystyle B}$, 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.
• Positive reducible: ${\displaystyle A}$ is positive reducible to ${\displaystyle B}$ if and only if ${\displaystyle A}$ is truth-table reducible to ${\displaystyle B}$ in a way that one can compute for every ${\displaystyle x}$ a formula consisting of atoms of the form ${\displaystyle B(0),B(1),...}$ such that these atoms are combined by and's and or's, where the and of ${\displaystyle a}$ and ${\displaystyle b}$ is 1 if ${\displaystyle a=1}$ and ${\displaystyle b=1}$ and so on.
• Enumeration reducibility: Similar to positive reducibility, relating to the effective procedure of enumerability from ${\displaystyle A}$ to ${\displaystyle B}$.
• 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 ${\displaystyle B(n)}$ are combined by exclusive or's. In other words, ${\displaystyle A}$ is linear reducible to ${\displaystyle B}$ if and only if a computable function computes for each ${\displaystyle x}$ a finite set ${\displaystyle F(x)}$ given as an explicit list of numbers such that ${\displaystyle x\in A}$ if and only if ${\displaystyle F(x)}$ contains an odd number of elements of ${\displaystyle B}$.

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.

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: A set ${\displaystyle A}$ is arithmetical in a set ${\displaystyle B}$ if ${\displaystyle A}$ is definable over the standard model of Peano arithmetic with an extra predicate for ${\displaystyle B}$. Equivalently, according to Post's theorem, A is arithmetical in ${\displaystyle B}$ if and only if ${\displaystyle A}$ is Turing reducible to ${\displaystyle B^{(n)}}$, the ${\displaystyle n}$th Turing jump of ${\displaystyle B}$, for some natural number ${\displaystyle n}$. The arithmetical hierarchy gives a finer classification of arithmetical reducibility.
• Hyperarithmetical reducibility: A set ${\displaystyle A}$ is hyperarithmetical in a set ${\displaystyle B}$ if ${\displaystyle A}$ is ${\displaystyle \Delta _{1}^{1}}$ definable (see analytical hierarchy) over the standard model of Peano arithmetic with a predicate for ${\displaystyle B}$. Equivalently, ${\displaystyle A}$ is hyperarithmetical in ${\displaystyle B}$ if and only if ${\displaystyle A}$ is Turing reducible to ${\displaystyle B^{(\alpha )}}$, the ${\displaystyle a}$th Turing jump of ${\displaystyle B}$, for some ${\displaystyle B}$-recursive ordinal ${\displaystyle a}$.
• Relative constructibility: A set ${\displaystyle A}$ is relatively constructible from a set ${\displaystyle B}$ if ${\displaystyle A}$ is in ${\displaystyle L(B)}$, the smallest transitive model of ZFC set theory containing ${\displaystyle B}$ and all the ordinals.

• Stanford Encyclopedia of Philosophy: Recursive Functions