O'Reilly logo

Theory of Computational Complexity, 2nd Edition by Ker-I Ko, Ding-Zhu Du

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required