PowerPoint Presentation
BU CS 332 – Theory of Computation
Lecture 17:
• Mapping Reductions
Reading:
Sipser Ch 5.3
Mark Bun
March 21, 2021
Reductions
A reduction from problem 𝐴 to problem 𝐵 is an algorithm
for problem 𝐴 which uses an algorithm for problem 𝐵 as a
subroutine
If such a reduction exists, we say “𝐴 reduces to 𝐵”
3/22/2021 CS332 – Theory of Computation 2
Positive uses: If 𝐴 reduces to 𝐵 and 𝐵 is decidable, then 𝐴
is also decidable
Ex. 𝐸DFA is decidable ⇒ 𝐸𝑄DFA is decidable
Negative uses: If 𝐴 reduces to 𝐵 and 𝐴 is undecidable,
then 𝐵 is also undecidable
Ex. 𝐸TM is undecidable ⇒ 𝐸𝑄TM is undecidable
What’s wrong with the following “proof”?
Bogus “Theorem”: 𝐴TM is not Turing-recognizable
Bogus “Proof”: Suppose for contradiction that there exists a
recognizer 𝑅 for 𝐴TM. We construct a recognizer for 𝐴TM:
On input 𝑀,𝑤 :
1. Run 𝑅 on input 𝑀,𝑤
2. If 𝑅 accepts, reject. Otherwise, accept.
This sure looks like a reduction from 𝐴TM to 𝐴TM
3/22/2021 CS332 – Theory of Computation 3
🚩🚩Warning🚩🚩
Mapping Reductions: Motivation
1. How do we formalize the notion of a reduction?
2. How do we use reductions to show that languages are
unrecognizable?
3. How do we protect ourselves from accidentally
“proving” bogus statements about recognizability?
3/22/2021 CS332 – Theory of Computation 4
Computable Functions
Definition:
A function 𝑓: Σ∗ → Σ∗ is computable if there is a TM 𝑀
which, given as input any 𝑤 ∈ Σ∗, halts with only 𝑓(𝑤) on
its tape. (“Outputs 𝑓(𝑤)”)
3/22/2021 CS332 – Theory of Computation 5
Computable Functions
Definition:
A function 𝑓: Σ∗ → Σ∗ is computable if there is a TM 𝑀
which, given as input any 𝑤 ∈ Σ∗, halts with only 𝑓(𝑤) on
its tape. (“Outputs 𝑓(𝑤)”)
Example 1: 𝑓 𝑥, 𝑦 = 𝑥 + 𝑦
Example 2: 𝑓 𝑀,𝑤 = 𝑀′ where 𝑀 is a TM, 𝑤 is a
string, and 𝑀’ is a TM that ignores its input and simulates
running 𝑀 on 𝑤
3/22/2021 CS332 – Theory of Computation 6
Mapping Reductions
Definition:
Language 𝐴 is mapping reducible to language 𝐵, written
𝐴 ≤m 𝐵
if there is a computable function 𝑓: Σ∗ → Σ∗ such that for
all strings 𝑤 ∈ Σ∗, we have 𝑤 ∈ 𝐴⟺ 𝑓(𝑤) ∈ 𝐵
3/22/2021 CS332 – Theory of Computation 7
Mapping Reductions
Definition:
Language 𝐴 is mapping reducible to language 𝐵, written
𝐴 ≤m 𝐵
if there is a computable function 𝑓: Σ∗ → Σ∗ such that for
all strings 𝑤 ∈ Σ∗, we have 𝑤 ∈ 𝐴⟺ 𝑓(𝑤) ∈ 𝐵
If 𝐴 ≤m 𝐵, which of the following is always true?
a) ҧ𝐴 ≤m 𝐵
b) 𝐴 ≤m ത𝐵
c) ҧ𝐴 ≤m ത𝐵
d) ത𝐵 ≤m ҧ𝐴
3/22/2021 CS332 – Theory of Computation 8
Decidability
Theorem: If 𝐴 ≤m 𝐵 and 𝐵 is decidable, then 𝐴 is also
decidable
Proof: Let 𝑀 be a decider for 𝐵 and let 𝑓: Σ∗ → Σ∗ be a
mapping reduction from 𝐴 to 𝐵. Construct a decider for 𝐴
as follows:
On input 𝑤:
1. Compute 𝑓(𝑤)
2. Run 𝑀 on input 𝑓(𝑤)
3. If 𝑀 accepts, accept. If it rejects, reject.
3/22/2021 CS332 – Theory of Computation 9
Undecidability
Theorem: If 𝐴 ≤m 𝐵 and 𝐵 is decidable, then 𝐴 is also
decidable
Corollary: If 𝐴 ≤m 𝐵 and 𝐴 is undecidable, then 𝐵 is also
undecidable
3/22/2021 CS332 – Theory of Computation 10
Old Proof: Equality Testing for TMs
𝐸𝑄TM = 𝑀1, 𝑀2 𝑀1, 𝑀2 are TMs and 𝐿 𝑀1 = 𝐿 𝑀2 }
Theorem: 𝐸𝑄TM is undecidable
Proof: Suppose for contradiction that there exists a decider 𝑅
for 𝐸𝑄TM. We construct a decider for 𝐴TM as follows:
On input 𝑀 :
1. Construct TMs 𝑀1, 𝑀2 as follows:
𝑀1 = 𝑀 𝑀2 = “On input 𝑥,
1. Ignore 𝑥 and reject”
2. Run 𝑅 on input 𝑀1, 𝑀2
3. If 𝑅 accepts, accept. Otherwise, reject.
This is a reduction from 𝐸TM to 𝐸𝑄TM
3/22/2021 CS332 – Theory of Computation 11
New Proof: Equality Testing for TMs
𝐸𝑄TM = 𝑀1, 𝑀2 𝑀1, 𝑀2 are TMs and 𝐿 𝑀1 = 𝐿 𝑀2 }
Theorem: 𝐸TM ≤m 𝐸𝑄TM hence 𝐸𝑄TM is undecidable
Proof: The following TM 𝑁 computes the reduction 𝑓:
On input 𝑀 :
1. Construct TMs 𝑀1, 𝑀2 as follows:
𝑀1 = 𝑀 𝑀2 = “On input 𝑥,
1. Ignore 𝑥 and reject”
2. Output 𝑀1, 𝑀2
3/22/2021 CS332 – Theory of Computation 12
Mapping Reductions: Recognizability
3/22/2021 CS332 – Theory of Computation 13
Theorem: If 𝐴 ≤m 𝐵 and 𝐵 is recognizable, then 𝐴 is also
recognizable
Proof: Let 𝑀 be a recognizer for 𝐵 and let 𝑓: Σ∗ → Σ∗ be a
mapping reduction from 𝐴 to 𝐵. Construct a recognizer
for 𝐴 as follows:
On input 𝑤:
1. Compute 𝑓(𝑤)
2. Run 𝑀 on input 𝑓(𝑤)
3. If 𝑀 accepts, accept. Otherwise, reject.
Unrecognizability
Theorem: If 𝐴 ≤m 𝐵 and 𝐵 is recognizable, then 𝐴 is also
recognizable
Corollary: If 𝐴 ≤m 𝐵 and 𝐴 is unrecognizable, then 𝐵 is
also unrecognizable
Corollary: If 𝐴TM ≤m 𝐵, then 𝐵 is unrecognizable
3/22/2021 CS332 – Theory of Computation 14
Recognizability and 𝐴TM
3/22/2021 CS332 – Theory of Computation 15
Let 𝐿 be a language. Which of the following is true?
a) If 𝐿 ≤m 𝐴TM, then 𝐿 is recognizable
b) If 𝐴TM ≤m 𝐿, then 𝐿 is recognizable
c) If 𝐿 is recognizable, then 𝐿 ≤m 𝐴TM
d) If 𝐿 is recognizable, then 𝐴TM ≤m 𝐿
Theorem: 𝐿 is recognizable if and only if 𝐿 ≤m 𝐴TM
Recognizability and 𝐴TM
3/22/2021 CS332 – Theory of Computation 16
Theorem: 𝐿 is recognizable if and only if 𝐿 ≤m 𝐴TM
Proof:
Example: Another reduction to 𝐸𝑄TM
3/22/2021 CS332 – Theory of Computation 17
𝐸𝑄TM = 𝑀1, 𝑀2 𝑀1, 𝑀2 are TMs and 𝐿 𝑀1 = 𝐿 𝑀2 }
Theorem: 𝐴TM ≤m 𝐸𝑄TM
Proof: The following TM 𝑁 computes the mapping reduction 𝑓:
What should the inputs and outputs to 𝑓 be?
a) 𝑓 should take as input a pair 𝑀1, 𝑀2 and output a pair 〈𝑀,𝑤〉
b) 𝑓 should take as input a pair 〈𝑀,𝑤〉 and output a pair 𝑀1, 𝑀2
c) 𝑓 should take as input a pair 𝑀1, 𝑀2 and either accept or reject
d) 𝑓 should take as input a pair 〈𝑀,𝑤〉 and either accept or reject
Example: Another reduction to 𝐸𝑄TM
3/22/2021 CS332 – Theory of Computation 18
𝐸𝑄TM = 𝑀1, 𝑀2 𝑀1, 𝑀2 are TMs and 𝐿 𝑀1 = 𝐿 𝑀2 }
Theorem: 𝐴TM ≤m 𝐸𝑄TM
Proof: The following TM 𝑁 computes the mapping reduction 𝑓:
On input 𝑀,𝑤 :
1. Construct TMs 𝑀1, 𝑀2 as follows:
𝑀1 = “On input 𝑥, 𝑀2 = “On input 𝑥,
2. Output 𝑀1, 𝑀2
Consequences of 𝐴TM ≤m 𝐸𝑄TM
1. Since 𝐴TM is undecidable, 𝐸𝑄TM is also undecidable
2. 𝐴TM ≤m 𝐸𝑄TM implies 𝐴TM ≤m 𝐸𝑄TM
Since 𝐴TM is unrecognizable, 𝐸𝑄TM is unrecognizable
3/22/2021 CS332 – Theory of Computation 19
𝐸𝑄TM itself is also unrecognizable
3/22/2021 CS332 – Theory of Computation 20
𝐸𝑄TM = 𝑀1, 𝑀2 𝑀1, 𝑀2 are TMs and 𝐿 𝑀1 = 𝐿 𝑀2 }
Theorem: 𝐴TM ≤m 𝐸𝑄TM hence 𝐸𝑄TM is unrecognizable
Proof: The following TM computes the reduction:
On input 𝑀,𝑤 :
1. Construct TMs 𝑀1, 𝑀2 as follows:
𝑀1 = “On input 𝑥, 𝑀2 = “On input 𝑥,
1. Ignore 𝑥 1. Ignore 𝑥 and reject”
2. Run 𝑀 on input 𝑤
3. If 𝑀 accepts, accept.
Otherwise, reject.”
2. Output 𝑀1, 𝑀2