Reducibility and Degrees of Unsolvability

Reducibility compares the difficulty of problems by transforming one into another, and grouping problems of equal difficulty produces the degrees of unsolvability that structure the world beyond the computable.

Definition

A problem reduces to another when an algorithm with access to a solver for the second can solve the first; problems that reduce to each other share a degree of unsolvability, and these degrees form an ordering measuring relative algorithmic difficulty.

Scope

This topic covers many-one and Turing reducibility, the use of reductions to prove undecidability, the Turing jump operation that produces strictly harder problems, the arithmetical hierarchy classifying problems by logical complexity, and central results of degree theory such as the existence of intermediate degrees.

Core questions

• How can we say one unsolvable problem is harder than another?
• How are reductions used both to prove undecidability and to organize problems?
• What does the Turing jump produce, and why is it always strictly harder?
• Are there problems strictly between the decidable and the halting problem?

Key theories

Reducibility and the Turing jump

Turing reducibility relates problems by oracle computation, and the jump of a problem, encoding halting relative to it, is always strictly more difficult, generating an unending tower of harder and harder problems.

Existence of intermediate degrees

The Friedberg–Muchnik theorem solved Post's problem by constructing computably enumerable problems that are undecidable yet strictly easier than the halting problem, using the priority method, showing the degrees have rich structure.

Clinical relevance

The reduction technique is the everyday workhorse for proving problems unsolvable or, in complexity theory, intractable: showing that a known hard problem reduces to a new one transfers the hardness, which is exactly how undecidability and NP-completeness results are established across mathematics and computer science.

History

Turing introduced oracle machines in 1939, and Post in 1944 framed the study of degrees of unsolvability and posed the problem of whether intermediate computably enumerable degrees exist. Friedberg and Muchnik independently solved it in 1956–1957 by inventing the priority method, which became a central technique of the subject.

Key figures

• Emil Post
• Alan Turing
• Richard Friedberg
• Albert Muchnik

Seminal works

• soare2016
• rogers1987

Frequently asked questions

What is a reduction, intuitively?

It is a way of solving one problem using a solver for another. If you can translate any instance of problem A into an instance of problem B so that the answers match, then B is at least as hard as A, and a solution to B yields a solution to A.

Are there problems harder than the halting problem?

Yes, infinitely many. Applying the Turing jump to the halting problem yields a strictly harder problem, and repeating the operation builds an endless hierarchy, so unsolvability comes in unbounded degrees rather than a single level.