HW8 Solutions - University Of Georgia CSCI 4510

Document Content and Description Below

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 u... ndecidable 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]

Last updated: 2 years ago

Preview 1 out of 3 pages