Courses

# Reduction Notes | EduRev

Created by: Vipul Dogra

## : Reduction Notes | EduRev

``` Page 1

Lecture 7
Page 2

Lecture 7
Reduction
“A is reducible to B” means I could solve A if I had a
subroutine for B
Ex:
Finding the max element in a list is reducible to sorting
pf: sort the list in increasing order, take the last element
(A big hammer for a small problem, but never mind...)
Page 3

Lecture 7
Reduction
“A is reducible to B” means I could solve A if I had a
subroutine for B
Ex:
Finding the max element in a list is reducible to sorting
pf: sort the list in increasing order, take the last element
(A big hammer for a small problem, but never mind...)
The Halting Problem
HALT
TM
= { <M,w> | TM M halts on input w }
Theorem: The halting problem is undecidable
Proof:
A = A
TM
, B = HALT
TM
Suppose I can reduce A to B.  We
already know A is undecidable, so must be that B is, too.
Suppose TM R decides HALT
TM
.  Consider S:
On input <M,w>, run R on it.  If it rejects, halt & reject; if it
accepts, run M on w; accept/reject as it does.
Then S decides A
TM
, which is impossible.  R can’t exist.
Page 4

Lecture 7
Reduction
“A is reducible to B” means I could solve A if I had a
subroutine for B
Ex:
Finding the max element in a list is reducible to sorting
pf: sort the list in increasing order, take the last element
(A big hammer for a small problem, but never mind...)
The Halting Problem
HALT
TM
= { <M,w> | TM M halts on input w }
Theorem: The halting problem is undecidable
Proof:
A = A
TM
, B = HALT
TM
Suppose I can reduce A to B.  We
already know A is undecidable, so must be that B is, too.
Suppose TM R decides HALT
TM
.  Consider S:
On input <M,w>, run R on it.  If it rejects, halt & reject; if it
accepts, run M on w; accept/reject as it does.
Then S decides A
TM
, which is impossible.  R can’t exist.
Halt?
M,w
Simulate
acc
acc rej
rej
R:
S:
Yes
Page 5

Lecture 7
Reduction
“A is reducible to B” means I could solve A if I had a
subroutine for B
Ex:
Finding the max element in a list is reducible to sorting
pf: sort the list in increasing order, take the last element
(A big hammer for a small problem, but never mind...)
The Halting Problem
HALT
TM
= { <M,w> | TM M halts on input w }
Theorem: The halting problem is undecidable
Proof:
A = A
TM
, B = HALT
TM
Suppose I can reduce A to B.  We
already know A is undecidable, so must be that B is, too.
Suppose TM R decides HALT
TM
.  Consider S:
On input <M,w>, run R on it.  If it rejects, halt & reject; if it
accepts, run M on w; accept/reject as it does.
Then S decides A
TM
, which is impossible.  R can’t exist.
Halt?
M,w
Simulate
acc
acc rej
rej
R:
S:
Yes
Another Way
Rather than running R on <M,w>, and manipulating that
answer, manipulate the input to build a new M’ so that