---
tag: Y6VV7N0FNE
kind: concept
name: Reduction (computability theory)
aliases: [reducibility-relation, reduction-recursion-theory]
sources:
  - wikipedia: en:9719800@r1353400901
    locator: Reduction (computability theory)
    note: adopted
    mention: wikipedia://en/9719800
    sections: [Summary]
same_as:
  wikidata: Q7306360
  wikipedia: Reduction (computability theory)
inventory: [MJX9D5T7SK]
---

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