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 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 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.
Read more about this topic: Reduction (recursion Theory)
Famous quotes containing the word relations:
“When one walks, one is brought into touch first of all with the essential relations between one’s physical powers and the character of the country; one is compelled to see it as its natives do. Then every man one meets is an individual. One is no longer regarded by the whole population as an unapproachable and uninteresting animal to be cheated and robbed.”
—Aleister Crowley (1875–1947)