Reduction (computability theory): Difference between revisions

Revision as of 02:38, 26 February 2007

Revision as of 02:43, 26 February 2007

Line 4:

== Reducibility relations==

A decision procedure for a set ''A'' of natural numbers is a function that, given a natural number ''n'' returns ''1'' if ''n'' is in ''A'' and returns ''0'' otherwise. In other words, a decision procedure computes (in some sense) the [[indicator function]] of a set. The decision procedure is not identified with the function it computes, but is viewed as a black box that performs some "procedure" (which may not be effective) in order to produce each output.

A '''reducibility relation''' is a binary relation on sets of natural numbers that is

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

* [[transitive relation|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 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 ''A'' is reducible to ''B'' if and only if aany (possibly noneffective) decision procedure for ''AB'' can be effectively converted to a decision procedure for ''BA''. The different reducibility relations vary in the methods they permit such a conversion process to use.

=== 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 recursion theory, these equivalence classess 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 ≤ be a reducibility relation and let '''A''' and '''B''' be two of its degrees. Then '''A''' ≤ '''B''' if and only if there is a set ''A'' in '''A''' and a set ''B'' in '''B''' such that ''A'' ≤ ''B''. This is equivalent to the property that for every set ''A'' in '''A''' and every set ''B'' in '''B''', ''A'' ≤ ''B'', because any two sets in ''A'' are equivalent and any two sets in ''B'' are equivalent. It is common, as shown here, to use boldface notation to denote degrees.

== Turing reducibility ==