CS 332: Elements of Theory of Computation Prof. Mark Bun
Boston University April 29, 2021
Test 3
� Read all the instructions on this page before beginning the exam.
� Your solutions must be scanned and uploaded to Gradescope by 5:00PM Eastern Daylight Time,
Thursday, May 6, 2021.
� We are flexible with the format in which you complete the exam and upload the solutions. Blank
space is provided if you wish to print the exam out and write your solutions on it, or if you wish
to download the PDF and fill it out on a tablet. You may also prepare your solutions on your
own paper as if you were completing a homework assignment. Both handwritten and typeset
solutions are allowed. Make sure to clearly indicate which problem you are solving, both on your
written solution and when you submit to Gradescope.
� This exam contains 6 problems, some with multiple parts. There is also one bonus problem
which will be accounted for in the same way as bonus homework problems. The test is worth
100 points.
� The exam is open-book in that you may freely consult the Sipser textbook, lecture notes and
videos posted online, past homework assignments and solutions, discussion worksheets, your own
class notes, and discussions on Piazza. You may not use any outside resources beyond those
listed here.
� You must complete the exam by yourself. No collaboration with anyone is permitted.
� You do not need to spend time and paper rederiving facts that we have studied. You may
cite known results and examples which were stated in lecture or proved in the main
body of the text. This does not include homework problems, discussion section problems, or
the solved exercises/problems in the text. You are, of course, free to use such results but you
have to prove them first.
� You will be graded not only on the correctness of your answer, but also on the clarity with which
you express it. Make your writing large and neat.
� If you need to ask a clarification question about one of the problems, please do so in an instructor-
only post on Piazza. If the course staff believes your question may be a common one, we will
change the settings of your post to be public to the class, keeping your identity anonymous.
� Good luck! We hope you have fun solving these problems.
1
Problem 1 (True, False, or Unknown, 20 points). Indicate whether each of the following statements
is true, false, or whether it is unknown whether it is true or false (e.g., it is equivalent to an open
question we’ve studied such as the P vs. NP problem). Justify your answer in two or three sentences.
No points will be given even for a correct answer if no justification is presented.
(a) If L is decidable in polynomial time on a 3-tape TM, then L is decidable in polynomial time
on a basic, single tape TM.
(b) Let L ∈ P be a set of binary strings. Then the language UnaryL = {1n | 〈n〉 ∈ L} (i.e., the
language consisting of the unary encodings of all strings w ∈ L) is also in P.
(c) Every regular language is in SPACE(n2).
(d) TIME(2n
2
) ⊆ NTIME(n).
(e) The language EDFA is NP-complete.
Problem 2 (Build-a-Language Workshop, 20 points). Identify a language satisfying each of the
requested conditions, or assert that no such language can exist. Justify your answer in two or
three sentences. No points will be given even for a correct answer if no justification is
presented.
(a) A is in NP, but A is not generated by a regular expression.
(b) B is Turing-recognizable, but B is not in EXP.
(c) ATM ≤m C, but C is not Turing-recognizable.
(d) D is in NP, but D is not decidable.
(e) E ≤p E.
Problem 3 (Finite TM, 12 points). Let FINTM = {〈M〉 |M is a TM such that L(M) is a finite language}.
Show that ATM ≤m FINTM and explain why this shows that FINTM is not Turing-recognizable.
Problem 4 (Dominating Set, 20 points). Given an undirected graph G, a dominating set is a set
of vertices S such that every vertex v /∈ S is adjacent to at least one vertex in S. For example, in
the cyclic graph with vertex set [4] and edge set {(1, 2), (2, 3), (3, 4), (4, 1)}, the set S = {1, 2} is a
dominating set, but S′ = {1} is not a dominating set.
(a) Describe a polynomial-time algorithm that, given a graph G, determines whether G has a
dominating set of size exactly 2. Briefly explain why your algorithm is correct and analyze
its runtime. (10 points)
(b) Generalize your algorithm to solve the following problem for any constant k: Given a graph
G, determine whether G has a dominating set of size exactly k. Again, briefly explain why
your algorithm is correct and analyze its runtime. (5 points)
(c) Let DS = {〈G, k〉 | G has a dominating set of size exactly k}. Determine whether or not the
following algorithm shows DS is in P, and explain your answer: On input 〈G, k〉, run the
algorithm from part (b) using parameter k and return the result. (5 points)
2
Problem 5 (Multiple Set Intersection, 25 points). Let S1, . . . , Sm ⊆ [n] and T ⊆ [n] be sets.
We say that T multisects S1, . . . , Sm if T ∩ Sj 6= ∅ for every j = 1, . . . ,m. For example, if
S1 = {1, 2, 3}, S2 = {3, 4, 5}, S3 = {6, 7}, S4 = {2, 3, 7}, then T = {3, 7} multisects S1, . . . , S4,
but T ′ = {1, 7} does not multisect S1, . . . , S4 because T ′ ∩ S2 = ∅. Define the language MS =
{〈S1, . . . , Sm, n, k〉 | there exists a set T ⊆ [n] with |T | ≤ k such that T multisects S1, . . . , Sm}.
(a) Show that MS ∈ NP. Describe your algorithm or verifier, explain why it is correct, and
analyze its runtime. (10 points)
(b) Show that V ERTEX −COV ER ≤p MS and use this to conclude that MS is NP-complete.
Describe your reduction, explain why it is correct, and analyze its runtime. (15 points)
Problem 6 (Limerick, 3 points). A limerick is a poem consisting of five lines. The first, second,
and fifth lines rhyme, while the third and fourth lines are shorter and share a different rhyme. For
example:
An algorithm quite far from trivial
For consistently setting each literal
Alas we did see
Unless NP is P
It can’t run in time polynomial.
Write a limerick that has something to do with the content of this class. Your limerick will
not be evaluated on artistic merit — it just has to (roughly) follow the rules about rhyming and
have something to do with what happened in CS 332. We may share some of our favorite limericks
anonymously on Piazza.
Problem 7 (Bonus). Define the complexity class coNP = {L | L ∈ NP}. Define the “tautology”
language TAUT = {〈ϕ〉 | ϕ is a boolean formula such that ϕ(x) = 1 for all assignments x}.
(a) Show that TAUT is coNP-complete under polynomial-time reductions. That is, show that
TAUT ∈ coNP and that every language in coNP is poly-time reducible to TAUT .
(b) Show that NP = coNP if and only if SAT ≤p TAUT .
3