Reduction (computability theory): Difference between revisions

Revision as of 21:24, 23 April 2021

Revision as of 01:07, 26 April 2021

Line 12:

=== 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 recursioncomputability 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 [[partial order|partially ordered]] by the relation in the following manner. Let <math>\leq</math> be a reducibility relation and let <math>C</math> and <math>D</math> be two of its degrees. Then <math>C\leq D</math> if and only if there is a set <math>A</math> in <math>C</math> and a set <math>B</math> in <math>D</math> such that <math>A\leq B</math>. This is equivalent to the property that for every set <math>A</math> in <math>C</math> and every set <math>B</math> in <math>D</math>, <math>A\leq B</math>, because any two sets in ''C'' are equivalent and any two sets in <math>D</math> are equivalent. It is common, as shown here, to use boldface notation to denote degrees.

Line 28:

*[[many-one reduction|Many-one reducibility]]: <math>A</math> is many-one reducible to <math>B</math> if there is a computable function <math>f</math> with <math>A(x) = B(f(x))</math> for all <math>x</math>.

*[[Truth table reduction|Truth-table reducible]]: <math>A</math> is truth-table reducible to <math>B</math> if <math>A</math> is Turing reducible to <math>B</math> via a single (oracle) Turing machine which produces a total function relative to every oracle.

*[[Truth table reduction|Weak truth-table reducible]]: <math>A</math> is weak truth-table reducible to <math>B</math> if there is a Turing reduction from <math>B</math> to <math>A</math> and a recursivecomputable function <math>f</math> which bounds the [[Turing reduction#The use of a reduction|use]]. Whenever <math>A</math> is truth-table reducible to <math>B</math>, <math>A</math> is also weak truth-table reducible to <math>B</math>, since one can construct a recursivecomputable 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: <math>A</math> is positive reducible to <math>B</math> if and only if <math>A</math> is truth-table reducible to <math>B</math> in a way that one can compute for every <math>x</math> a formula consisting of atoms of the form <math>B(0), B(1), ...</math> such that these atoms are combined by and's and or's, where the and of <math>a</math> and <math>b</math> is 1 if <math>a = 1</math> and <math>b = 1</math> and so on.

*[[Enumeration reducibility]]: Similar to positive reducibility, relating to the effective procedure of [[enumerability]] from <math>A</math> to <math>B</math>''.''

Line 34:

*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 <math>B(n)</math> are combined by [[XOR gate|exclusive or's]]. In other words, <math>A</math> is linear reducible to <math>B</math> if and only if a computable function computes for each <math>x</math> a finite set <math>F(x)</math> given as an explicit list of numbers such that <math>x \in A</math> if and only if <math>F(x)</math> contains an odd number of elements of <math>B</math>.

Many of these were introduced by Post (1944). Post was searching for a non-[[recursiveComputable set|recursivecomputable]], [[recursivelycomputably 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.

=== Bounded reducibilities ===

Line 42:

{{main|Reduction (complexity)}}

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. Thus if a set <math>A</math> is [[computable set|decidable]] then <math>A</math> is reducible to any set <math>B</math> under any of the strong reducibility relations listed above, even if <math>A</math> is not polynomial-time or exponential-time decidable. This is acceptable in the study of recursioncomputability 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 reduction|polynomial-time reducibility]]; a set ''A'' is polynomial-time reducible to a set <math>B</math> if there is a polynomial-time function ''f'' such that for every <math>n</math>, <math>n</math> is in <math>A</math> if and only if <math>f(n)</math> is in <math>B</math>. 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.