Reduction (recursion Theory) - Reductions Stronger Than Turing Reducibility

Reductions Stronger Than Turing Reducibility

The strong reducibilities include

• One-one reducibility: A is one-one reducible to B if there is a computable one-to-one function f with A(x) = B(f(x)) for all x.
• Many-one reducibility: 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 reducible: 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 reducible: 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, 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.