Reduction (computability theory)

Key takeaways

Reduction (computability theory) belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Reduction (computability theory) to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Reduction (computability theory) from memory before moving on to harder problems.

Reference excerpt

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 {\displaystyle A} and B {\displaystyle B} of natural numbers, is it possible to effectively convert a method for deciding membership in B {\displaystyle B} into a method for deciding membership in A {\displaystyle A} ? If the answer to this question is affirmative then A {\displaystyle A} is said to be reducible to B {\displaystyle B} . The study of reducibility notions is motivated by the study of decision problems. For many notions of reducibility, if any noncomputable set is reducible to a set A {\displaystyle A} then A {\displaystyle A} must also be noncomputable. This gives a powerful technique for proving that many sets are noncomputable.

Reducibility relations A reducibility relation is a binary relation on sets of natural numbers that is

Reflexive: Every set is reducible to itself. Transitive: If a set A {\displaystyle A} is reducible to a set B {\displaystyle B} and B {\displaystyle B} is reducible to a set C {\displaystyle C} then A {\displaystyle A} is reducible to C {\displaystyle C} . These two properties imply that reducibility is a preorder on the powerset of the natural numbers. Not all preorders are studied as reducibility notions, however. The notions studied in computability theory have the informal property that A {\displaystyle A} is reducible to B {\displaystyle B} if and only if any (possibly noneffective) decision procedure for B {\displaystyle B} can be effectively converted to a decision procedure for A {\displaystyle A} . The different reducibility relations vary in the methods they permit such a conversion process to use.

Degrees of a reducibility relation Every reducibility relation (in fact, every preorder) induces an equivalence relation on the powerset of the natural numbers in which two sets are equivalent if and only if each one is reducible to the other. In computability theory, these equivalence classes are called the degrees of the reducibility relation. For example, the Turing degrees are the equivalence classes of sets of naturals induced by Turing reducibility. The degrees of any reducibility relation are partially ordered by the relation in the following manner. Let ≤ {\displaystyle \leq } be a reducibility relation and let C {\displaystyle C} and D {\displaystyle D} be two of its degrees. Then C ≤ D {\displaystyle C\leq D} if and only if there is a set A {\displaystyle A} in C {\displaystyle C} and a set B {\displaystyle B} in D {\displaystyle D} such that A ≤ B {\displaystyle A\leq B} . This is equivalent to the property that for every set A {\displaystyle A} in C {\displaystyle C} and every set B {\displaystyle B} in D {\displaystyle D} , A ≤ B {\displaystyle A\leq B} , because any two sets in C are equivalent and any two sets in D {\displaystyle D} are equivalent. It is common, as shown here, to use boldface notation to denote degrees.

Turing reducibility

The most fundamental reducibility notion is Turing reducibility. A set A {\displaystyle A} of natural numbers is Turing reducible to a set B {\displaystyle B} if and only if there is an oracle Turing machine that, when run with B {\displaystyle B} as its oracle set, will compute the indicator function (characteristic function) of A {\displaystyle A} . Equivalently, A {\displaystyle A} is Turing reducible to B {\displaystyle B} if and only if there is an algorithm for computing the indicator function for A {\displaystyle A} provided that the algorithm is provided with a means to correctly answer questions of the form "Is n {\displaystyle n} in B {\displaystyle B} ?". Turing reducibility serves as a dividing line for other reducibility notions because, according to the Church–Turing thesis, it is the most general reducibility relation that is effective. Reducibility relations that imply Turing reducibility have come to be known as strong reducibilities, while those that are implied by Turing reducibility are weak reducibilities. Equivalently, a strong reducibility relation is one whose degrees form a finer equivalence relation than the Turing degrees, while a weak reducibility relation is one whose degrees form a coarser equivalence relation than Turing equivalence.

Reductions stronger than Turing reducibility The strong reducibilities include

… excerpt ends here. Continue reading the full article.

Worked examples

Example 1 — a first encounter with Reduction (computability theory)

Start with the simplest possible case. Write down what Reduction (computability theory) claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Reduction (computability theory) before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Reduction (computability theory) ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Reduction (computability theory)

In research: Reduction (computability theory) appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Reduction (computability theory) in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Reduction (computability theory) is common in secondary-school and first-year university syllabi. It links to neighbouring topics Reduction (complexity), so understanding it makes those chapters shorter.
In everyday life: Look for Reduction (computability theory) outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Reduction (computability theory) in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Reduction (computability theory) means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Reduction (computability theory) out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Reduction (computability theory) in simple terms?

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 {\displaystyle A} and B {\displaystyle B} of natural numbers, is it possible to effectively convert a method for d…

Why does Reduction (computability theory) matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Reduction (computability theory)?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Reduction (computability theory).