Content deleted Content added
m Proposed merge: https://en.wikipedia.org/wiki/Talk:Reduction_(complexity)#Untitled Tags: Reverted Visual edit |
Closing stale April merge proposal; no case made, no support over many months |
||
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 <math>A</math> and <math>B</math> of natural numbers, is it possible to effectively convert a method for deciding membership in <math>B</math> into a method for deciding membership in <math>A</math>? If the answer to this question is affirmative then <math>A</math> is said to be '''reducible to''' <math>B</math>.
| |||