18.

405 Advanced Complexity Theory Due: March 07, 2007

Problem Set 2
Name: John Hawksley Collaborated with: T. Johnson, A. Lerer, A. Deckelbaum

Problem 1: Circuit-Size Hierarchy

Circuits of size f (n)logf (n) can compute all functions of size log(f (n)logf (n)), of which
there are 2f (n)logf (n) . Meanwhile, there are only 2o(f (n))log(o(f (n))) circuits of size o(f (n))
and therefore these circuits must compute fewer functions when n is sufficiently large, by
the definition of little-o notation. Since we know that circuits of size o(2n /n) cannot already
compute all functions on n inputs, we are done. 

Problem 2: Poly-size Circuits

Suppose that NP 6⊆ P/poly . Then any language L ∈P/poly −P works, since no problem in
P/poly can be NP-hard. An example is the Halting problem with inputs in unary.
Otherwise NP ⊆P/poly . Unless P=NP we can choose L in NP such that L is not in P and
also not NP-complete. By construction L ∈P/poly − P and is not NP-hard. 
logn
We construct a machine M to decide a language L ∈ T IM E(2O(n ) )−P/poly , by diag-
onalization:
M = “On input w, enumerate circuits of |w| inputs with size ≤ 2n /n. Simulate each circuit
on every string of length |w|, and record the results. If w is the jth string of size |w|,
then stop when we have found the circuit that decides the jth unique formula computed by
circuits in the enumeration. If we run out of circuits, output anything. Otherwise, simulate
the selected circuit on input w, and output the opposite result.”
There are 2n circuits of size ≤ 2n /n. To simulate each circuit takes time ≤ 22n /n2 , by
tableaus. So we run in the allotted time. Now consider a circuit family in P/poly . Since its
circuit size order of growth function is polynomial in n, but size of circuits we enumerate
grows exponentially (and we never overflow the 2n possible values of w for a given input
length, M will output a different result than the circuit family on some input w with |w|
sufficiently large. 

Problem 3: CNF, DNF, and Branching Programs

Assume that any function expressable as a k-DNF formula and an l-CNF formula, has
a branching program of depth f (k, l) for some function f . Then consider a function
g : {0, 1}n → {0, 1} that can be expressed as a (k + 1)-DNF and an l-CNF.

1-1
Both forms of g compute the same function, so a non-satisfying assignment of variables
to any single clause of the CNF must also prevent any clause of the DNF from being satis-
fied. Therefore, each clause of the CNF shares some variable with every clause of the DNF.
So g reduces to an OR over all 2l assignments of a single clause of the CNF formula, where
in each case the remaining formula reduces to a function that can be expressed as a (k + 1)-
DNF and an l-CNF, and the depth f (k + 1, l) = f (k, l) + 1. Since any satisfying assignment
of variables to a clause of DNF formula must force all clauses of the corresponding CNF
formula to be satisfied, we can similarly reduce f (k, l + 1) = f (k, l) + 1.

Finally, f (1, 1) = 1 since any function that expresses as a 1-DNF and a 1-CNF formula
must have only one important input, which completes the induction. 

Problem 4: k-SAT when there are many

A polytime algorithm for 2SAT is known. Given a k-CNF formula φ (k > 2), we reduce to
the problem of solving the same problem on a (k − 1)-CNF, and conclude by induction.
k
Given ε, let n0 be any constant satisfying ( 2 2−1
k )
n0 < ε. The reduction greedily selects

clauses of φ, such that each new clause is disjoint from (i.e. shares no variables with) any
previously selected clause. Let there be n disjoint clauses chosen at which point all other
clauses each share a some variable with one of the n. We condition on n:

If n > n0 , then the probability that each of the n clauses computes to 1 given a ran-
dom assignment of inputs is at most ε, by our choice of n0 . Therefore the probability that
the full φ computes to 1 given a random assignment, is no more than ε, and we can halt
with the n clauses as proof that fewer than an ε fraction of assignments are satisfying.

Otherwise, n ≤ n0 , so at most a constant number of clauses are in the disjoint set. There-
fore, we can try all possible assignments to the variables in the disjoint clauses, and record
each set of inputs that sets each of the disjoint to 1. Each remaining clause shares some
variable with a clause in the disjoint set, so any of these sets of inputs reduces the remaining
clauses to a (k − 1)-CNF formula, completing the proof. 

Problem 5: Majority

To prove {M ajn }n 6∈ AC 0 , we construct a circuit to show that PARITY is AC 0 -reducible

On n inputs, the circuit first ”guesses” the number that are ones, by sending all inputs
into each of n + 1 subcircuits at the next level. The kth subcircuit ”verifies” that there are
indeed k ones by routing each of the inputs together with a quantity of hardwired zeros or

1-2
ones into a MAJORITY gate, and also to a second MAJORITY gate with yet another hard-
wired one. For each subcircuit, the quantity and type of hardwired inputs to MAJORITY
are such that, if there are k ones, the first MAJORITY gate sees an equal number of zeros
and ones as input. Thus, an XOR of the two MAJORITY gates serves as the verifier of k.
Each k-subcircuit concludes with an AND of its verifier bit with the predetermined output
of PARITY with k ones as input. Finally, the circuit ends with an OR of the outputs of
each of the k + 1 subcircuits. Since only the correct output bit is considered, this circuit
decides PARITY, and we have shown that {M ajn }n 6∈ AC 0 .

Observe that the above circuit extends to any function that depends only on the num-
ber of 1’s in the input (by changing the predetermined output bits), hence the function
computing MOD-3 also reduces to MAJORITY. Yet we know that MOD-3 is not in the
AC 0 closure of PARITY, so neither can be MAJORITY. 

Problem 6: A Lower Bound via Communication Complexity

Consider a 1-tape Turing machine M deciding PALINDROME. For some input of length
n, and all k, the machine must pass between slots k and k + 1 on the tape at least θ(n).
Suppose otherwise for some k and all inputs. Then consider what happens if we replace the
substring in slots k + 1 through n − k by a known palindrome, letting the substring (1, k)
be α and the substring (n − k + 1, n − k) be β. Then the full string is a palindrome iff
α = β −1 . This in mind, we can construct a protocol to decide EQn with fewer than θ(n)
communication complexity:

Machine A sees the part of M’s tape starting with k and moving leftwards, and machine B
sees the M’s tape starting with k+1 and moving rightwards. Each machine emulates M when
the head is on their side of the tape. When the head would cross from k to k + 1, machine A
sends a message to machine B to begin running at cell k + 1, including the current state of
M. Similarly if the head crosses in the other direction. So the number of bits of the message
sent is constant in the number of states of M. Since M decides PALINDROME by crossing
between k and k + 1 fewer than θ(n) times, machines A and B can confirm α = β −1 with
better than θ(n) message space (i.e., starting with β −1 , machine B can begin by prepending
it with a known palindrome of the appropriate length to reach the above starting situation).

So we have shown that M must pass between slots k and k + 1 on the tape at least θ(n)
times for all k, on some input of length n. Since there are n such choices of k, M runs in
time at least nθ(n) = Ω(n2 ). 

1-3