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:
“All of life and human relations have become so incomprehensibly complex that, when you think about it, it becomes terrifying and your heart stands still.”
—Anton Pavlovich Chekhov (1860–1904)