12.1 Reducibility

Reducibility is a way to compare problems by asking whether one problem can be solved using another.

Suppose we have two decision problems, $A$ and $B$. Each problem asks whether an input belongs to a certain set:

or

We say that $A$ reduces to $B$ if a method for solving $B$ would also give us a method for solving $A$.

In informal terms:

means:

The direction matters. If $A \leq B$, then $B$ is at least as powerful as $A$. A solver for $B$ can be used to solve $A$.

Many-One Reducibility

One common kind of reducibility is many-one reducibility.

We write:

if there is a computable function $f$ such that:

This means we can transform every question about $A$ into one question about $B$.

The function $f$ is called a reduction function.

The process looks like this:

Then instead of asking whether $x \in A$, we ask whether $f(x) \in B$.

If the answer to $f(x) \in B$ is yes, then the answer to $x \in A$ is yes. If the answer is no, then the answer to $x \in A$ is no.

So $B$ solves $A$ after a computable translation.

Example Pattern

Suppose $A$ is the problem:

and $B$ is another problem about programs.

To show:

we build a computable transformation:

where $e$ is an instance of problem $B$.

Then we prove:

This is the standard structure of a reduction proof.

Turing Reducibility

Many-one reducibility allows one computable translation and one query to $B$. Turing reducibility is more flexible.

We write:

if $A$ can be decided by a Turing machine with oracle access to $B$.

An oracle for $B$ is an idealized device that answers questions of the form:

in one step.

A machine deciding $A$ may ask the oracle many questions while it runs. It may choose later questions depending on earlier answers.

So $A \leq_T B$ means:

or equivalently:

Every many-one reduction gives a Turing reduction:

The reverse implication does not hold in general. Turing reductions allow more interaction with the oracle.

Why Reducibility Matters

Reducibility lets us transfer impossibility results.

If:

and $A$ is undecidable, then $B$ must also be undecidable.

Why? If $B$ were decidable, then we could solve $A$ by reducing $A$ to $B$ and then deciding $B$. That would contradict the undecidability of $A$.

So the proof pattern is:

Therefore:

This is one of the most important uses of reductions.

Reduction Direction

The most common beginner mistake is reversing the direction.

To prove that $B$ is hard, reduce a known hard problem $A$ to $B$:

This says: if we could solve $B$, then we could solve $A$.

Since $A$ cannot be solved, $B$ cannot be solved either.

So the hard problem goes on the left, and the new problem goes on the right.

Reducibility as a Preorder

Reducibility behaves like a comparison relation.

First, every problem reduces to itself:

This is reflexivity.

Second, reductions compose. If:

and

then:

This is transitivity.

Together, these properties make reducibility a preorder.

It may happen that:

and:

Then $A$ and $B$ have the same computational difficulty under that reducibility.

For Turing reducibility, we write:

when:

This equivalence relation leads to Turing degrees, which are studied in the next section.