Definition. Reductions [reductions]

Say we have two problems.

Problem 1.: Shoot a red elephant.
Problem 2.: Shoot a blue elephant.

We can say that $P_{1}$ reduces to $P_{2}$ if we can design an algorithm for solving $P_{1}$ that uses $P_{2}$ .

$P_{1}\underset{T}{\leq}P_{2}$
$P_{1}$ reduces to $P_{2}$
$P_{1}$ can be solved in terms of $P_{2}$
$P_{1}$ can be solved using $P_{2}$ as a Subroutine

IMPORTANT: Note the order! This is easy to flip-flop!

Given our original problems: this means that the problem of shooting a red elephant can be solved by shooting a blue elephant.

What else does this tell us?

If $P_{2}$ is easy, then $P_{1}$ is easy
If $P_{1}$ is hard, then $P_{2}$ is hard (we’ll use this idea a lot)
$P_{1}$ is no harder than $P_{2}$
$P_{2}$ is at least as hard as $P_{1}$

We can similarly talk about languages this way. $L_{1} \leq L_{2}$ means:

deciding $L_{1}$ is no harder than deciding $L_{2}$ , or
deciding $L_{2}$ is at least as hard as deciding $L_{1}$ .

Example. Showing the Halting problem to be undecidable

Last time: $A_{\text{TM}}$ is undecidable.

$A_{\text{TM}} = \left\{ {\left\langle {M,w} \right\rangle:M\ \text{accepts}\ w} \right\}$
$\text{HALT}_{\text{TM}} = \left\{ {\left\langle {M,w} \right\rangle:M\ \text{halts on input}\ w} \right\}$

Recall: $\text{HALT}_{\text{TM}}$ is recognizable

You can create a Turing machine $U$ that takes an $\left\langle {M,w} \right\rangle$ and simulate it: if $U$ halts, our original Turing machine $M$ accepts

We want to show that $A_{\text{TM}}\underset{T}{\leq}\text{HALT}_{\text{TM}}$ .

Proof. (by contradiction.)

Suppose there is a Turing machine $R$ that decides $\text{HALT}_{\text{TM}}$ (it doesn’t exist).

We want to use $R$ to design a Turing machine $S$ that decides $A_{\text{TM}}$ .

Design:

Use $R$ to reject if the input runs forever
Otherwise, simply simulate the input (it is now guaranteed to be decidable)

So we can, and we do, and we arrive at a contradiction: as we know there is no such decider for $A_{\text{TM}}$ .

Then as $A_{\text{TM}}$ reduces to $\text{HALT}_{\text{TM}}$ : $\text{HALT}_{\text{TM}}$ is at least as hard as $A_{\text{TM}}$ , which is undecidable.

So $\text{HALT}_{\text{TM}}$ is undecidable.

Aside.

Reduction can go both ways! $A_{\text{TM}}$ reduces to $\text{HALT}_{\text{TM}}$ , and vice versa. There are (probably) problems that cannot be related, however.

Example. Showing that $E_{\text{TM}}$ is undecidable

We will show by reduction: by reducing $A_{\text{TM}}$ to $E_{\text{TM}}$ .

In other words, we will construct a Turing-machine for deciding $A_{\text{TM}}$ that uses $E_{\text{TM}}$ as a subroutine.

$A_{\text{TM}} = \left\{ {\left\langle {M,w} \right\rangle:M\ \text{accepts}\ w} \right\}$
$E_{\text{TM}} = \{\left\langle M \right\rangle:M\ \text{is a Turing machine and}\ L(M)\ \text{is empty}$ (i.e. $M$ accepts nothing)

Proof.

Assume we have a decider $R$ that decides $E_{\text{TM}}$ .

Idea: create a new Turing machine $N$ with $M,w$ hardcoded inside.

if y != w: reject
if y == w: then run $M$ on input $w$
So the language is either $w$ or $\varnothing$ .

Simulating a Turing machine $S$ on input $x$ :

if $x$ not of form $\left\langle {M,w} \right\rangle$ then reject
Construct the Turing-machine $N$ above
Run $R$ on input $N$
If $R$ accepts, then we know $M$ does not accept $w$
If $R$ accepts, $S$ rejects, and if $R$ rejects, $S$ accepts.