Content deleted Content added
m Manually reviewed edit to replace magic words per local rfc |
No edit summary |
||
Line 1:
{{other uses|Reduction (disambiguation)}}
In [[computability theory]], many '''reducibility relations''' (also called '''reductions''', '''reducibilities''', and '''notions of reducibility''') are studied. They are motivated by the question: given sets ''A'' and ''B'' of natural numbers, is it possible to effectively convert a method for deciding membership in ''B'' into a method for deciding membership in ''A''? If the answer to this question is affirmative then ''A'' is said to be '''reducible to''' ''B''.
| |||