CS 332: Theory of Computation Prof. Mark Bun
Boston University April 7, 2021
Homework 7 – Due Friday, April 16, 2021 at 11:59 AM
Reminder Collaboration is permitted, but you must write the solutions by yourself without as-
sistance, and be ready to explain them orally to the course staff if asked. You must also identify
your collaborators and write “Collaborators: none” if you worked by yourself. Getting solutions from
outside sources such as the Web or students not enrolled in the class is strictly forbidden.
Note You may use various generalizations of the Turing machine model we have seen in class, such as
TMs with two-way infinite tapes, stay-put, or multiple tapes. If you choose to use such a generalization,
state clearly and precisely what model you are using.
Problems There are 4 required problems.
1. (Odd-Length TM) Let OLTM = {〈M〉| M is a TM that accepts all strings whose length is a odd
number and rejects all other strings}.
(a) Your first goal in this problem is to use a mapping reduction from ATM to show that OLTM
is not Turing-recognizable. Describe what the inputs and outputs of this mapping reduction
should be. (As in lecture 17 check-in, question 1.) (3 points)
(b) Describe a TM computing a mapping reduction from ATM to OLTM and explain why this TM
is correct. (8 points)
(c) Explain why part (b) implies that OLTM is not Turing-recognizable. (3 points)
(d) Use a (different) mapping reduction to prove that OLTM is not Turing-recognizable (i.e., OLTM
is not co-Turing-recognizable). (12 points)
2. (Asymptotic Notation) Use to the formal definitions of O and o notation to prove the following
statements.
(a) Prove that n2(3 log7 n + n) = O(n
3) by showing that there exists a constant c > 0 and a
natural number n0 such that n
2(3 log7 n + n) ≤ cn3 for every n ≥ n0. (6 points)
(b) Prove that 3n = o(n2) by showing that for every constant c > 0, there exists a natural number
n0 such that 3n ≤ cn2 for every n ≥ n0. (6 points)
(c) Prove that 3
√
n = 2o(n) using the fact that f(n) = o(g(n)) if limn→∞ f(n)/g(n) = 0. (6 points)
3. (Review of asymptotic notation) This problem will be graded automatically by Gradescope.
Please enter your answers manually by completing the assignment Homework 7-Problem 3. For
each of the following, select true or false using the radio buttons on Gradescope. All logarithms are
base 2 unless otherwise stated. (1 point each)
1
(a) 1337 = O(n2)
(b) n10 = O(n9 log n)
(c) n log n + 10n = o(n2)
(d) 4n = O(2n)
(e) 4n = 2O(n)
(f) 22
n
= O(2n
2
)
(g) 2n = o(n2)
(k) 106 = o(n)
(l) 2 log n = o(log n)
(m) 1
3
= o(1)
(n) 2n = o(4n)
(o) n5 = O(32log2 n)
(p) log n = O(log(log n))
(q) 32
n
= o(23
n
)
4. (Polynomial-Time Algorithms)
(a) Let A = {w ∈ {0, 1}∗ | w contains at least as many 0’s as 1’s}. Give an implementation-level
description of a basic, single-tape Turing machine M that decides A. Briefly explain why
your TM correctly decides A. Analyze the running time and space usage of M to show that
A ∈ TIME(n log n) and A ∈ SPACE(n). (12 points)
(b) An undirected graph G = (V,E) is triangle-free if for every triple of vertices u, v, w, it is
not the case that (u, v), (v, w), and (w, u) are all edges in the graph. Let TF = {〈G〉 |
G is triangle-free}. Show that TF ∈ P by i) giving a high-level description of a polynomial-
time algorithm deciding TF , ii) analyzing the correctness of your algorithm, and iii) explaining
why your algorithm runs in polynomial time.
You don’t need to specify the exact polynomial runtime that your algorithm runs in, since this
may depend on implementation details that are suppressed in a high-level description. Just
give a convincing argument that the runtime is polynomial as in the examples in Chapter 7.2
of Sipser. (12 points)
(c) The Fibonacci sequence is defined by the following recurrence: F0 = 0, F1 = 1, and Fn =
Fn−1 + Fn−2 for every n ≥ 2. Prove that there is no polynomial-time algorithm that takes as
input a natural number n (written in binary) and outputs (i.e., writes to its tape) the number
Fn (again, written in binary). (8 points)
Hint: How big can the numbers Fn get as a function of n?
(d) Give a high-level description of a polynomial-time algorithm that takes as input a natural
number n (written in unary) and outputs the number Fn (written in binary). Explain why
your algorithm is correct and why it runs in polynomial time. (10 points)
Hint: You can use without proof the fact that Turing machines can perform basic arithmetic
operations on binary numbers, like addition, in polynomial time.
2