CS 535: Complexity Theory, Fall 2020 Homework 3
Due: 8:00PM, Friday, September 25, 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 1 (Hierarchy theorems and padding). Recall the “padding argument” proof that complexity collapses such as P = NP would scale up to EXP = NEXP. (Or equivalently, the complexity separation EXP ̸= NEXP would scale down to P ̸= NP.)
(a) Show that if NTIME(n) ⊆ DTIME(n2), then NTIME(n2) ⊆ DTIME(n4). (b) Show that for every k ≥ 1, we have P ̸= NTIME(nk).
Hint: Part (a) is not directly useful here, but the idea behind it is.
Problem 2 (NP vs. coNP relative to an oracle). The Baker-Gill-Solovay Theorem (Theo- rem 3.7 in Arora-Barak) shows that there is an oracle A relative to which PA ̸= NPA. This problem will walk you through a proof of the stronger result that NPA ̸= coNPA for some oracle. (The writeup is long, but the parts you have to fill in should be short!)
(a) A DNF formula D is an OR of “terms,” where each term is an AND of literals. The width of a DNF is the maximum number of literals appearing in any term and the size is the number of terms. For example, (x1 ∧x2)∨(x2 ∧x3 ∧x4) is a DNF of width 3 and size 2.
Believe it or not, the whole proof rests on the following simple combinatorial fact1: The function ANDN(x1,…,xN) = x1∧···∧xN cannot be computed by a DNF D(x1,…,xN) of width < N. Prove this fact.
(b) Another way to think of an oracle A is as an infinitely long vector, indexed by binary strings. Thatis,forz∈{0,1}∗,letAz =1ifz∈AandAz =0ifz∈/A. Recallthatto query A, a TM can write a string z to its oracle tape and receive the bit Az.
Let f = {fn : {0, 1}2n → {0, 1}} be a sequence of Boolean functions. Define the unary language2
Lf(A) = {1n | fn(A) = 1}.
1Well, in the same way that Baker-Gill-Solovay rests on the fact that ORN cannot be computed by a “decision tree” of depth < N.
2The Learn-from-Anywhere language.
1
Let fn(A) = ANDz∈{0,1}n(Az), so that Lf(A) consists of the strings 1n for which z ∈ A for all z ∈ {0, 1}n. Show that Lf (A) ∈ coNPA for every oracle A.
(c) Now our job is construct an oracle A for which Lf(A) ∈/ NPA. We’ll do this by first arguing that the output of an NPA machine is just a DNF applied to the oracle A.
Let M be a nondeterministic oracle Turing machine running in time T(n). Show that for every n ∈ N there exists a DNF formula Dn of width at most T (n) and size at most 2T (n) such that for every oracle A,
MA(1n)=1 ⇐⇒ Dn(A)=1, again regarding A as an infinite vector (Az)z∈{0,1}∗.
Hint 1: When run on an input of length n, the machine M can query the oracle at most T(n) times.
Hint 2: A binary tree of depth T has at most 2T leaves.
(d) Next we diagonalize against all nondeterministic machines running in time T(n) = 2n/10 to instantiate the oracle A. Let M1, M2, . . . be an enumeration of such machines, with each machine appearing infinitely often in the list. We construct an oracle A∗ (details below) such that for every machine Mi in the enumeration, there exists an input 1ni such that MA∗(1ni) = 1 ⇐⇒ 1ni ∈/ L (A∗).
if
Using this guarantee of the oracle A∗, put everything together to conclude that NPA∗ ̸=
coNPA∗ .
Hint: Details for how to construct A∗ are provided below for your interest and enjoyment,
but you do not need to understand anything about how A∗ works to solve the problem.
We construct A∗ iteratively as follows. We initialize A∗ to be the empty language, and in each round i, commit to including or excluding strings of a certain length ni in A∗. We choose ni large enough so that no string of length ni has had its fate decided in any previous round.
Let Dni be the DNF formula guaranteed by part (c) capturing the behavior of machine Mi on input 1ni . By part (a), there exists an oracle A(i) such that
Dni (A(i)) ̸= fni (A(i)).
Actually, something stronger is true. Since fni (A) only depends on the values of Az for
z ∈ {0,1}ni, we may assume that A(i) = A∗ for every |z| < n . zzi
Now for all of the (finitely many) z for which the variable Az appears in the DNF Dni , set A∗ = A(i). That is, for each such z, commit to including z in A∗ if z ∈ A(i) and
zz
commit to excluding z from A∗ if z ∈/ A(i). Then by part (b),
MA∗(1ni)=1 ⇐⇒ D (A∗)=1 ⇐⇒ f (A∗)=0 ⇐⇒ 1ni ∈/ L (A∗). i ni ni f
2
Problem 3 (*Bonus Problem*, NP vs. coNP relative to a random oracle). Are oracles that separate NP from coNP rare, or are they common? In this problem, you’ll show that NPA ̸= coNPA not only for some contrived oracle A, but for almost all oracles. This whole problem is all just for fun and you can solve any of the subparts independently assuming the previous ones.
(a) For N ∈ N, let N = sw where w = Θ(logN) and s = Θ(N/logN) are chosen so that (1 − 2−w )s = 1 ± o(1). Define the function CN (x1,1 , . . . , xs,w ) = s w xi,j .
2 i=1 j=1 If we take fn = C2n , show that Lf (A) ∈ coNPA for every oracle A.
(b) Show that there is a constant c such that for every DNF D of width at most cN/logN, Pr [D(x) ̸= CN (x)] ≥ 0.1.
x∼{0,1}N
(c) Let A ⊆ {0,1}∗ be a random oracle. That is, for every string z ∈ {0,1}∗, include z in A independently with probability 1/2. Show that NPA ̸= coNPA with probability at least 0.99 over the choice of the random oracle A.3
3Complexity class separations satisfy a zero-one law, which implies that the probability of a separation is actually 1.
3