Circuit complexity: Difference between revisions

Revision as of 02:29, 27 October 2006

Revision as of 02:32, 27 October 2006

Line 4:

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, ... </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 (complexity)]], [[TC0]] and [[NC (complexity)]].

==References==

Line 11 ⟶ 13:

[[Category:Computational complexity theory]]

[[Category:Circuit complexity]]

{{math-stub}}