5.8: A finite computational task is specified by a function f:\{0,1\}^n \rightarrow \{0,1\}^m. We can model a computational process using Boolean circuits (of varying gate sets) or straight-line program. Every function can be computed by many programs. We say that f \in \ensuremath{\mathit{SIZE}}_{n,m}(s) if there exists a NAND circuit of at most s gates (equivalently a NAND-CIRC program of at most s lines) that computes f. Every function f:\{0,1\}^n \rightarrow \{0,1\}^m can be computed by a circuit of O(m \cdot 2^n/n) gates. Many functions such as multiplication, addition, solving linear equations, computing the shortest path in a graph, and others, can be computed by circuits of much fewer gates. In particular there is an O(s \log^2 s)-size circuit that computes the map C,x \mapsto C(x) where C is a string describing a circuit of s gates. However, the counting argument shows there do exist some functions f:\{0,1\}^n \rightarrow \{0,1\}^m that require \Omega(m \cdot 2^n /n) gates to compute.
{}