Theory of Computational Complexity, 2nd Edition

Regarding an AC⁰ circuit of depth d as a depth- circuit of the type considered in Theorem 6.37, we obtain the following.

Corollary 6.38

For sufficiently large n, the parity function p_n cannot be computed by a depth-d circuit of size at most .

This corollary completes the proof of Theorem 6.34. Actually, we can obtain a better lower bound than that in Corollary 6.38 by using the argument in the proof of Theorem 6.37 once again. We leave it as an exercise.

The rest of this section is devoted to the proof of the Switching Lemma.

First, we notice that each AND-OR circuit corresponds to a CNF and each OR-AND circuit corresponds to a DNF. Recall, from Chapter 5, that for any Boolean function f, D(f) denotes the minimum depth of a decision tree computing f. Also recall that in a decision tree computing f, each path from root to a leaf with label 1 corresponds to an implicant. Therefore, if , then f can be computed by an OR-AND circuit of bottom fan-in at most s. The above observation shows that to prove the Switching Lemma, it suffices to prove that for any AND-OR circuit G with bottom fan-in at most t,

The following is a stronger form.

Lemma 6.39

Let G be an AND-OR circuit ...