Reduction (computability theory)

Summary

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$.