CS 332: Theory of Computation Professor Mark Bun Boston University April 20, 2020
Homework 9 – Due Monday, April 27, 2020 before 2:00PM
Reminder Collaboration is permitted, but you must write the solutions by yourself without assistance, and be ready to explain them orally to the course staff if asked. You must also identify your collaborators. Getting solutions from outside sources such as the Web or students not enrolled in the class is strictly forbidden.
Exercises Please practice on the following exercises and solved problems in Chapter 7 and Chap- ter 8: 7.23, 7.33, 8.1, 8.4, 8.6. The material they cover may appear on exams.
Problems There are 5 mandatory problems.
1. (Hamiltonian Path) Read the reduction from 3SAT to HAMPATH on page 314 of Sipser.
(a) Is this construction also a valid polynomial-time reduction from 2SAT to HAMPATH ?
(b) Draw the graph G that the reduction outputs on input formula φ = (x ̄ ∨ y) ∧ (x ∨ y ̄).
For both satisfying assignments of φ, give a corresponding Hamiltonian path in G.
(c) Draw the graph G that the reduction outputs on input formula φ = (x ∨ y) ∧ (x ̄ ∨ y ̄) ∧ (x ̄ ∨ y) ∧ (x ∨ y ̄). Argue that G does not have a Hamiltonian path (not relying on the fact that we already proved that the reduction is correct).
(d) Why would a polynomial-time reduction from HAMPATH to 2SAT have surprising implications, but a reduction in the other direction does not? Hint: You may use the result of Problem 7.51(b) in Sipser, without proof, to answer this question.
2. (Inheritance) Alice and Bob are siblings who have inherited a collection of marbles from an eccentric relative. There are k distinct kinds of marbles, but the collection may contain several of each kind of marble. The collection is partitioned into m boxes. Each box contains two bags of marbles such that within each bag, no marbles are duplicated. The will stipulates that Alice and Bob divide the collection as follows: For every box of marbles, Alice is to receive one bag from that box, and Bob is to receive the other bag. Their goal is to determine whether there is a way to partition the collection in this way such that both Alice and Bob obtain a complete set of all k kinds of marbles.
For example, suppose k = 4 and the kinds of marbles are labeled 1,2,3,4. Suppose there are m = 3 boxes of marbles B1 = ({1, 2}, {1}), B2 = ({2}, {1, 4}), B3 = ({3, 4}, {3}). Then if Alice takes the first bag from box B1, the second bag from box B2, and the second bag from box B3 (and Bob takes the second bag from B1, the first bag from B2 and the first bag from B3), then both Alice and Bob receive complete sets of marbles.
Consider the problem MARBLES = {⟨k,B1,…,Bm⟩ | there exists a partition of the collection such that Alice and Bob both receive complete sets of marbles}. Show that this problem is NP-complete.
1
3. (EQNFA) Recall that EQNFA = {⟨N1, N2⟩ | N1 and N2 are NFAs and L(N1) = L(N2)}. Show that EQNFA is in PSPACE.
4. A hypercube walk is a sequence of strings s1, s2, . . . , sk ∈ {0, 1}n such that each string differs from the previous string in exactly one bit. For example, the following is a hypercube walk starting with “0011” and ending with “1100” where every intermediate string is a member of the regular language {s ∈ {0, 1}4 | s contains at least one 0 and at least one 1}:
0011, 0111, 0110, 1110, 1100.
Let WALKDFA = {⟨M,s,t⟩| M is a DFA and L(M) contains a hypercube walk of strings, starting with s and ending with t}. Show that WALK DFA is in PSPACE.
5. For each of the following, give a language B (if it exists) satisfying the stated property. Explain why your language B satisfies the given property, or explain why no such language B can exist.
(a) B ≤P SAT and B is not NP-complete. (b) SAT ≤P B and B is not NP-complete.
(c) SAT ≤P B and B is not NP-hard. (d) B is regular and NP-complete.
2