Discrete Structures

2. (15)

Let 𝑆𝑈𝐵𝑆𝐸𝑇𝐷𝐹𝐴 = {⟨𝑀1,𝑀2⟩ | 𝑀1 and 𝑀2 are DFAs and 𝐿(𝑀1) ⊆ 𝐿(𝑀2)}.

a.

(5)

Show that 𝑆𝑈𝐵𝑆𝐸𝑇𝐷𝐹𝐴 is decidable.

b.

(10)

Show that 𝑆𝑈𝐵𝑆𝐸𝑇𝐷𝐹𝐴 ∈ 𝑃.

3. (15)

We say that a Turing machine is verbose on s if, at the completion of its computation on s, it leaves at least as many non-blank characters on the left of the tape as s has total characters.

Let VERBOSETM = { <M, w> | M is a TM and is verbose on s }.

Show that VERBOSETM is undecidable by reduction from ATM. Do not use Rice’s theorem.

4. (15)

Let POWERTM = { <M> | M is a TM, and for all s ∈ L(M), |s| is a power of 2 }.

Show that POWERTM is undecidable by reduction from ATM. Do not use Rice’s Theorem.

5. (20)

Given a set S of integers, we say that S can be partitioned if it can be split into two disjoint sets U and V whose sums are equal – in other words, we can take sets 𝑈 and 𝑉 so that 𝑈 ∪ 𝑉 = 𝑆, 𝑈 ∩ 𝑉 = ∅, and ∑𝑢∈𝑈 𝑢 = ∑𝑣∈𝑉 𝑣.

Let PARTITION = { <S> | S can be partitioned }.

a.

(5)

Show that PARTITION  NP by writing either a verifier or an NDTM.

b. (15) Show that PARTITION is NP-complete by reduction from SUBSET-SUM.