CS 4510 Automata and Complexity Released: 4/11/2022
Homework 8: Undecidability, P, and NP
Due:4/18/2022
1. Undecidability Reductions (10 points each)
Show that each of the following languages is undecidable using red
...
CS 4510 Automata and Complexity Released: 4/11/2022
Homework 8: Undecidability, P, and NP
Due:4/18/2022
1. Undecidability Reductions (10 points each)
Show that each of the following languages is undecidable using reductions from known
undecidable languages. (No points will be given for any other method of proof.) You
may use as the source of the reduction any language shown in class or in the book to
be undecidable.
(a) L1 = {⟨M⟩ | |L(M)| = 5}, the problem of deciding whether a machine accepts
exactly 5 strings.
Solution.
We reduce from HALT. In other words, given an input ⟨M⟩, x, we must construct
a new machine M′
such that M′ accepts exactly 5 strings if and only if M halts on
input x. We claim that the following definition of M′
satisfies these requirements:
M′ on input y:
i. Simulate M on x
ii. If y = 0 or 1 or 00 or 000000 or
10101010100011110101000111111100011: accept y
iii. else reject y
We prove that f(⟨M⟩, x) = ⟨M′
⟩ is a mapping reduction from HALT to L1:
• ⟨M⟩, x ∈ HALT → ⟨M′
⟩ ∈ L1
Suppose M halts on x. Then M′ finishes step i and reaches step ii. In step
ii, there are exactly five possibilities for y to be are accepted, and all other
strings are rejected. So |L(M′
)| = 5.
• ⟨M′
⟩ ∈ L1 → ⟨M⟩, x ∈ HALT
Suppose M′ accepts exactly 5 strings. It can only accept in step ii, which
means that it must reach step ii for at least 5 possible inputs. But then
for those inputs M′ must finish step i, meaning that M must terminate on
input x.
(b) L2 = {(⟨M⟩,⟨N⟩) | M accepts ⟨N⟩ and N accepts ⟨M⟩}, the problem of deciding,
given two machines, whether they accept each other’s descriptions.
Solution.
We construct a mapping reduction from HALT to L2. Our input has the form
⟨M⟩, x, and our output has the form ⟨M′
⟩,⟨N′
⟩, such that M halts on x if and
only if M′ and N′ accept each other’s descriptions.
8: Undecidability, P, and NP-1
[Show More]