Boolean Circuit

Definition

A Boolean circuit C “computes” a (finite) function \(f:\{ 0,1\} ^n\mapsto \{ 0,1\} ^m\) over De Morgan basis
A circuit ensembles is an infinite family of circuits \(\mathcal{A}=\{ A_n\} _{n\in N}\). \(A_n\) has n input bits, \(\mathcal{A}\) has m bit output, if each \(A_n\) has \(m(n)\) output bits (i.e., m is a function from N to N, might be constant, e.g., m(n) = 1). Circuit ensemble can handle any input length, i.e., compute any (even infinite) functions, but the description size is infinite!.