CS 535: Complexity Theory, Fall 2020 Homework 6
Due: 8:00PM, Friday, October 23, 2020.
Reminder. Homework must be typeset with LATEX preferred. Make sure you understand the course collaboration and honesty policy before beginning this assignment. Collaboration is permitted, but you must write the solutions by yourself without assistance. You must also identify your collaborators. Assignments missing a collaboration statement will not be accepted. Getting solutions from outside sources such as the Web or students not enrolled in the class is strictly forbidden.
Problem 0 (Term Paper). Now would be a good time to start thinking about the term paper assignment: what topic/paper you might be interested in writing about, and who you might want to work with. Instructions for the term paper are here: https://cs-people. bu.edu/mbun/courses/535_F20/handouts/term_paper.pdf and a list of suggested topics is here: https://piazza.com/class/keda2wyieyz10e?cid=277.
Problem 1 (Exponential-Size Circuits for Every Function). In this problem, you will prove that every Boolean function f : {0,1}n → {0,1} can be computed by a circuit of size O(2n/n). As we’ll see, this is essentially tight: in fact, “most” functions require circuits of size Ω(2n/n).
(a) First show that every Boolean function f(x1, . . . , xn) can be written in the form (xn ∧ f0(x1,…,xn−1))∨(xn∧f1(x1,…,xn−1))forsomefunctionsf0,f1 :{0,1}n−1 →{0,1}. (2 points)
(b) Use part (a) recursively to show that every function f : {0, 1}k → {0, 1} is computed by a circuit of size O(2k). (2 points)
(c) There are exactly 22k different functions f : {0, 1}k → {0, 1}. Combine this fact with part (b) and another recursive application of part (a) to show that every function f : {0, 1}n → {0, 1} for n ≥ k can be computed a circuit of size O(2n−k) + O(2k · 22k ). Hint: You can assume each gate has unbounded fan-out, so you can “reuse” the output of a subcircuit as many times as you want. (4 points)
(d) Set k appropriately in part (c) to conclude that every Boolean function f : {0, 1}n → {0,1} is computed by a circuit of size O(2n/n). (2 points)
Problem 2 (More Time-Space Tradeoffs). In class (and in Arora-Barak) we saw that NTIME(n) ̸⊆ TISP(n1.2,n0.2), and hence SAT cannot be solved by a deterministic TM running in, say, time O(n1.1) and space O(n0.1) simultaneously. In this problem, you’ll see how far you can push the technique to get different tradeoffs. Assume every function you encounter is time- and space-constructible.
1
(a) Generalize Claim 5.11.1 in Arora-Barak to prove that for T(n) ≥ n2 and S(n) ≥ logn, √
we have TISP(T,S) ⊆ Σ2TIME( TS). (3 points)
(b) Generalize Claim 5.11.2 in Arora-Barak to prove that if NTIME(n) ⊆ DTIME(nc) for
some c > 1, then Σ2TIME(f(n)) ⊆ NTIME((f(n))c). (3 points)
(c) First we’ll see how large we can make the time requirement. Use parts (a) and (b) to prove that for every c < √2, there exists a δ > 0 such that NTIME(n) ̸⊆ TISP(nc,nδ). You don’t have to show it, but this implies that SAT cannot be solved by an algorithm using O(n1.41…) time and no(1) space. Hint: Note that δ is allowed to depend on c. You’ll want to choose δ small enough so that c(c + δ) < 2. (2 points)
(d) Now we’ll see how far we can push the space requirement. Prove that for every c < 1, there exists a δ > 0 such that NTIME(n) ̸⊆ TISP(n1+δ,nc). This result implies that SAT cannot be solved by an algorithm using n1+o(1) time and O(n0.999) space. Hint: This time, choose δ small enough so that (c + 1 + δ)(1 + δ) < 2. (2 points)
Problem 3 (*Bonus* Improved Time-Space Tradeoffs). Now let’s see how we can get even better tradeoffs by repeatedly trading alternations for time. Note that by combining Prob- lems 2(a) and (b), we get the statement: If NTIME(n) ⊆ DTIME(nc) for some c > 1, then TISP(T,S) ⊆ NTIME((TS)c/2).
(a) Suppose NTIME(n) ⊆ DTIME(nc) for some c > 1. Use the above statement to show that TISP(T,S) ⊆ coNTIME((TS2)c2/(2+c)). Hint: Let C0,Cf be the start and accept configurations of a deterministic TM running in time T. Then Cf is reachable from C0 in T time steps iff for all C′ ̸= Cf, we have that C′ is not reachable from C0 in T time steps.
(b) Conclude that NTIME(n) ̸⊆ TISP(nc, no(1)) whenever c3 < 2 + c, i.e., c < 1.521 . . . .
(c) Generalize the above argument inductively to show that NTIME(n) ̸⊆ TISP(nc, no(1))
whenever c(c − 1) < 1, i.e., c < φ = 1.618 . . . .
2