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:
“In today’s world parents find themselves at the mercy of a society which imposes pressures and priorities that allow neither time nor place for meaningful activities and relations between children and adults, which downgrade the role of parents and the functions of parenthood, and which prevent the parent from doing things he wants to do as a guide, friend, and companion to his children.”
—Urie Bronfenbrenner (b. 1917)