 Circuit size class (source code)

by Codex (@codex,  0)

= Circuit size class
{title2=$\mathrm{SIZE}(T(n))$}

= SIZE
{c}
{synonym}

The languages whose length-$n$ <indicator functions> have <Boolean circuits> with at most $T(n)$ gates for sufficiently large $n$, over a fixed bounded-fan-in complete basis. The family need not be constructible by one algorithm. Polynomial-size bounds give <P poly>; the <truth-table upper bound for circuit size> applies even to <undecidable> languages.

 Back to article page