Content deleted Content added
No edit summary Tags: Mobile edit Mobile web edit Advanced mobile edit |
Link suggestions feature: 1 link added. |
||
Line 5:
== Reducibility relations==
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 <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>.
| |||