Circuit complexity: Difference between revisions

Revision as of 11:22, 30 October 2009

Revision as of 19:50, 8 December 2009

Line 3:

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.

The circuit-size (respectively circuit-depth) complexity of a Boolean function ''f'' is the minimal size (respectively minimal depth) of any circuit computing ''f''. The goal of circuit complexity is to determine this optimal size/depth for natural families of Boolean functions. Most often the challenge involves the study of the [[asymptotic analysis|asymptotic behavior]] of size or depth complexity for sequences of Boolean functions <math>f_1, f_2, ...\dots </math> where each <math>f_n</math> is a function of ''n'' bits.

[[Complexity class]]es defined in terms of Boolean circuits include [[AC0|AC⁰]], [[AC (complexity)|AC]], [[TC0|TC⁰]] and [[NC (complexity)|NC]].

Line 9:

==Uniformity==

Boolean circuits are one of the prime examples of so-called [[uniformity (complexity)|non-uniform]] [[abstract machine|models of computation]] in the sense that inputs of different lengths are processed by different circuits, in contrast with uniform models such as [[Turing machine]]s where the same computational device is used for all possible input lengths. An individual [[computational problem]] is thus associated with a particular ''family'' of Boolean circuits <math>C_1, C_2, ...\dots </math> where each <math>C_n</math> is the circuit handling inputs of ''n'' bits. A [[uniformity (complexity)|uniformity]] condition is often imposed on these families, requiring the existence of some [[computational resource|resource-bounded]] Turing machine which, on input ''n'', produces a description of the individual circuit <math>C_n</math>. When this Turing machine has a running time polynomial in ''n'', the circuit family is said to be P-uniform. The stricter requirement of [[DLOGTIME]]-uniformity is of particular interest in the study of shallow-depth circuit-classes such as AC⁰ or TC⁰.

===Polynomial-time uniform===