Content deleted Content added
m "recursive" => "computable" per discussion here: https://en.wikipedia.org/wiki/Wikipedia_talk:WikiProject_Mathematics#Proposal:_change_terminology_from_%22recursive%22_to_%22computable%22 |
m Proposed merge: https://en.wikipedia.org/wiki/Talk:Reduction_(complexity)#Untitled Tags: Reverted Visual edit |
||
Line 1:
{{other uses|Reduction (disambiguation)}}{{Merge to|Reduction (complexity)|date=April 2021}}
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>.
| |||