Reduction (computability theory): Difference between revisions

Revision as of 04:56, 10 January 2021

Revision as of 21:24, 23 April 2021

Line 8:

* [[Reflexive relation|Reflexive]]: Every set is reducible to itself.

* [[transitive relation|Transitive]]: If a set <math>A</math> is reducible to a set <math>B</math> and <math>B</math> is reducible to a set <math>C</math> then <math>A</math> is reducible to <math>C</math>.

These two properties imply that a 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 <math>A</math> is reducible to <math>B</math> if and only if any (possibly noneffective) decision procedure for <math>B</math> can be effectively converted to a decision procedure for <math>A</math>. The different reducibility relations vary in the methods they permit such a conversion process to use.

=== Degrees of a reducibility relation ===

Line 37:

=== Bounded reducibilities ===

A '''bounded''' form of each of the above strong reducibilities can be defined. The most famous of these is bounded truth-table reduction, but there are also bounded Turing, bounded weak truth-table, and others. These first three are the most common ones and they are based on the number of queries. For example, a set <math>A</math> is bounded truth-table reducible to <math>B</math> if and only if the Turing machine <math>M</math> computing <math>A</math> relative to <math>B</math> computes a list of up to <math>n</math> numbers, queries <math>B</math> on these numbers and then terminates for all possible oracle answers; the value <math>n</math> is a constant independent of <math>x</math>. The difference between bounded weak truth-table and bounded Turing reduction is that in the first case, the up to <math>n</math> queries have to be made at the same time while in the second case, the queries can be made one after the other. For that reason, there are cases where <math>A</math> is bounded Turing reducible to <math>B</math> but not weak truth-table reducible to <math>B</math>.

=== Strong reductions in computational complexity ===

Line 47:

== Reductions weaker than Turing reducibility ==

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 <math>A</math> is arithmetical in a set <math>B</math> if <math>A</math> is definable over the standard model of [[Peano arithmetic]] with an extra predicate for <math>B</math>. Equivalently, according to [[Post's theorem]], ''A'' is arithmetical in <math>B</math> if and only if <math>A</math> is Turing reducible to <math>B^{(n)}</math>, the <math>n</math>th [[Turing jump]] of <math>B</math>, for some natural number <math>n</math>. The [[arithmetical hierarchy]] gives a finer classification of arithmetical reducibility.

* [[Hyperarithmetical reducibility]]: A set <math>A</math> is hyperarithmetical in a set <math>B</math> if <math>A</math> is <math>\Delta^1_1</math> definable (see [[analytical hierarchy]]) over the standard model of Peano arithmetic with a predicate for <math>B</math>. Equivalently, <math>A</math> is hyperarithmetical in <math>B</math> if and only if <math>A</math> is Turing reducible to <math>B^{(\alpha)}</math>, the <math>a</math>th [[Turing jump]] of <math>B</math>, for some <math>B</math>-[[recursive ordinal]] <math>a</math>.