On previous notes, it’s shown that every function $f: \{0,1\}^n \to \{0,1\}^m$ has a boolean circuit computing it by size of at most $O(n\cdot m \cdot 2^n)$

In fact, every function has a circuit of size $O(\frac{m \cdot 2^n}{n})$

For instance, the function ADD has a boolean circuit of size $O(n)$ and MULT has a boolean circuit of size $O(n)^2$

<aside> <img src="/icons/light-bulb_gray.svg" alt="/icons/light-bulb_gray.svg" width="40px" /> Main Goal for This Note: Different functions require different gates to compute

</aside>

We can view circuits themselves as $\{0,1\}^*$ strings, in other words, we can view circuits as inputs

Def “General Purpose Computers”: Computers that are not specific to any task

Once we can represent circuits as strings, we are able to get:

<aside> <img src="/icons/light-bulb_gray.svg" alt="/icons/light-bulb_gray.svg" width="40px" /> Theorem: Every (n, m, s) NAND-Circuit can be represented by a Boolean string of length $O(slog(n+s))$

</aside>

To describe a circuit, we need to at least contains the following information

To represent the type of each gate(like whether if it’s an output), we need to have to contain the information about index of the nodes that represent the output(so we have total of $m$ such elements)

To specify connections between gates, we need to have pairs of information. So we could have a list of pairs, where list[i] is the pair of nodes that are into the ith node

Example: