Circuit complexity: Difference between revisions

Revision as of 16:06, 22 September 2010

Revision as of 17:47, 29 March 2011

Line 1:

In [[theoretical computer science]], '''Circuit complexity''' is a topicbranch inof [[computational complexity theory]], a branch of [[theoretical computer science]]in which classifies [[Boolean function]]s are classified according to the amountsize or depth of [[computationalBoolean resourcecircuits]]s needed tothat compute them. In circuit complexity, these resources are size and depth of [[Boolean circuit]]s.

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.