Skip to Main Content
Theory of Computational Complexity, 2nd Edition
book

Theory of Computational Complexity, 2nd Edition

by Ding-Zhu Du, Ker-I Ko
June 2014
Intermediate to advanced content levelIntermediate to advanced
512 pages
17h 55m
English
Wiley
Content preview from Theory of Computational Complexity, 2nd Edition

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

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Theory of Computation

Theory of Computation

George Tourlakis

Publisher Resources

ISBN: 9781118594971Purchase book