Reduction (computability theory)
≈ 5 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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.
For many notions of reducibility, if any noncomputable set is reducible to a set A then A must also be noncomputable. This gives a powerful technique for proving that many sets are noncomputable.
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.
For many notions of reducibility, if any noncomputable set is reducible to a set A then A 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: 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 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 A is reducible to B if and only if any (possibly noneffective) decision procedure for B can be effectively converted to a decision procedure for A . The different reducibility relations vary in the methods they permit such a conversion process to use.
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 that 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 computable function f that 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 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: 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.
Enumeration reducibility: Similar to positive reducibility, relating to the effective procedure of enumerability from A to 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 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 \in 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-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.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1353400901 under CC BY-SA 4.0; modifications have been made.