Microsoft PowerPoint – CS332-Lec17-ann
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. is decidable is decidable
Negative uses: If reduces to and is undecidable,
then is also undecidable
Ex. is undecidable is undecidable
What’s wrong with the following “proof”?
Bogus “Theorem”: is not Turing‐recognizable
Bogus “Proof”: Suppose for contradiction that there exists a
recognizer for . We construct a recognizer for :
On input :
1. Run on input
2. If accepts, reject. Otherwise, accept.
This sure looks like a reduction from to
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
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
if there is a computable function ∗ ∗ such that for
all strings ∗, we have
If , which of the following is always true?
a)
b)
c)
d)
3/22/2021 CS332 ‐ Theory of Computation 8
Decidability
Theorem: If 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 and is decidable, then is also
decidable
Corollary: If and is undecidable, then is also
undecidable
3/22/2021 CS332 ‐ Theory of Computation 10
Old Proof: Equality Testing for TMs
Theorem: is undecidable
Proof: Suppose for contradiction that there exists a decider
for . We construct a decider for as follows:
On input :
1. Construct TMs , as follows:
= = “On input 𝑥,
1. Ignore 𝑥 and reject”
2. Run on input
3. If accepts, accept. Otherwise, reject.
This is a reduction from to
3/22/2021 CS332 ‐ Theory of Computation 11
New Proof: Equality Testing for TMs
Theorem: hence is undecidable
Proof: The following TM computes the reduction :
On input :
1. Construct TMs , as follows:
= = “On input 𝑥,
1. Ignore 𝑥 and reject”
2. Output
3/22/2021 CS332 ‐ Theory of Computation 12
Mapping Reductions: Recognizability
3/22/2021 CS332 ‐ Theory of Computation 13
Theorem: If 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 and is recognizable, then is also
recognizable
Corollary: If and is unrecognizable, then is
also unrecognizable
Corollary: If , then is unrecognizable
3/22/2021 CS332 ‐ Theory of Computation 14
Recognizability and
3/22/2021 CS332 ‐ Theory of Computation 15
Let be a language. Which of the following is true?
a) If , then is recognizable
b) If , then is recognizable
c) If is recognizable, then
d) If is recognizable, then
Theorem: is recognizable if and only if
Recognizability and
3/22/2021 CS332 ‐ Theory of Computation 16
Theorem: is recognizable if and only if
Proof: