Regarding an AC0 circuit of depth d as a depth-c06-math-1430 circuit of the type considered in Theorem 6.37, we obtain the following.

Corollary 6.38

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 c06-math-1439, 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

Get Theory of Computational Complexity, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.