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

Chapter 6

Circuit Complexity

We introduce in this chapter Boolean circuits as a nonuniform computational model. We demonstrate a close relation between the notion of Circuit-size complexity and TM time complexity. Two important exponential lower bound results are proved. The exponential lower bound for monotone circuits is proved by the technique of combinatorial approximation, and the exponential lower bound for constant-depth circuits is proved by the probabilistic method. The NC hierarchy is introduced as a model for computational complexity of parallel computation. The related notion of P-completeness is also presented.

6.1 Boolean Circuits

A Boolean circuit is an acyclic digraph of which each node with no in-edge is labeled by a variable or a Boolean constant 0 or 1 and each other node is labeled by a Boolean operator: negation, disjunction (OR), or conjunction (AND). The nodes labeled by variables are the input nodes, and the nodes labeled by Boolean operators are called logical gates. For each logical gate, its fan-in is the number of its in-edges (or inputs) and its fan-out is the number of its out-edges. We do not restrict the fan-out of a gate, but we sometimes restrict the fan-in of a gate. For a circuit computing a Boolean function, we assume that there exists a unique node of the circuit that has no out-edge; this node gives the output of the circuit and is called the output gate. Given a Boolean assignment to the variables, the circuit computes the function ...

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