Proof By Reduction

A proof by reduction involves showing that some other, solved problem can be transformed into the current problem to be solved. Proofs by reduction are used in undecidability proofs for certain problems over computational models.

Definition §

Reduction

Let $A$ and $B$ be two problems that need to be solved. Then, we say $A$ reduces to $B$ or:

$$A\le B⟺B{⊢}_{\psi }A$$

That is, assuming we have a solution of $B$, we can transform that solution with logical steps to a solution for $A$.

• $B$ is the more complex problem.
• More formally, given a proof system $\psi$, we can create a proof assuming $B$ and concluding $A$.

Decidability & Recognisability §

When talking about computational problems related to Turing machines, we have:

$$A\le B⟺\text{A decider DA for A can be constructed given a decider DB for B}$$

(If we are talking about the decidability of problems!)

This also leads to the two theorems below:

Theorems §

T1: Reduction preserves undecidability ^t1

Let $A,B$ be two problems. Then:

$$A\le B⟹(\text{A is undecidable}⟹\text{B is undecidable})$$

T2: Reduction preserves undecidability ^t2

Let $A,B$ be two problems. Then:

$$A\le B⟹(\text{A is unrecognisable}⟹\text{B is unrecognisable})$$

Examples §

Transclude of Accept