# 12.1 Reducibility

## 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:

$$
x \in A
$$

or

$$
x \in B
$$

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:

$$
A \leq B
$$

means:

$$
A \text{ is no harder than } B
$$

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:

$$
A \leq_m B
$$

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

$$
x \in A \quad \Longleftrightarrow \quad f(x) \in B
$$

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:

$$
x
\longmapsto
f(x)
$$

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:

$$
\text{Does program } M \text{ halt on input } w?
$$

and $B$ is another problem about programs.

To show:

$$
A \leq_m B
$$

we build a computable transformation:

$$
(M,w) \mapsto e
$$

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

Then we prove:

$$
M \text{ halts on } w
\quad \Longleftrightarrow \quad
e \in B
$$

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:

$$
A \leq_T B
$$

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:

$$
y \in B?
$$

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:

$$
A \text{ is computable relative to } B
$$

or equivalently:

$$
B \text{ has enough information to decide } A
$$

Every many-one reduction gives a Turing reduction:

$$
A \leq_m B \quad \Longrightarrow \quad A \leq_T B
$$

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:

$$
A \leq B
$$

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:

$$
A \leq B
$$

$$
A \text{ is undecidable}
$$

Therefore:

$$
B \text{ is undecidable}
$$

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

$$
A \leq 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:

$$
A \leq A
$$

This is reflexivity.

Second, reductions compose. If:

$$
A \leq B
$$

and

$$
B \leq C
$$

then:

$$
A \leq C
$$

This is transitivity.

Together, these properties make reducibility a **preorder**.

It may happen that:

$$
A \leq B
$$

and:

$$
B \leq A
$$

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

For Turing reducibility, we write:

$$
A \equiv_T B
$$

when:

$$
A \leq_T B
\quad \text{and} \quad
B \leq_T A
$$

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