Circuit complexity: Difference between revisions

Revision as of 17:47, 29 March 2011

Revision as of 17:48, 29 March 2011

Line 1:

In [[theoretical computer science]], '''Circuitcircuit complexity''' is a branch of [[computational complexity theory]] in which [[Boolean function]]s are classified according to the size or depth of [[Boolean circuits]] that compute them.

A Boolean circuit with ''n'' input [[bit]]s is a [[directed acyclic graph]] in which every node (usually called ''gates'' in this context) is either an input node of [[in-degree]] 0 labeled by one of the ''n'' input bits, an [[AND gate]], an [[OR gate|OR]] or a [[NOT gate]]. One of these gates is designated as the output gate. Such a circuit naturally computes a function of its ''n'' inputs. The size of a circuit is the number of gates it contains and its depth is the maximal length of a path from an input gate to the output gate.