Lesson 5

Now that we have a model of computation and a measure of complexity, it is natural to ask: what is the size of the smallest circuit that computes a given Boolean function? The two circuits we considered above (Half Adder and Full Adder) are optimal (i.e., there are no circuits of smaller size that compute the same functions), although we haven’t proven this. In general, finding minimal-size circuits even for simple functions is a challenging task. In 1963, Leo Hartman found the circuit complexity of all Boolean functions of three variables over the basis \(\{\operatorname{NAND}\}\), and in 1977, Frank Liang found the circuit complexity of all functions of four variables over the basis \(B_{2}\), whereas in 2008 Donald Knuth computed the circuit complexity of all functions from \(B_{5}\) in the same basis. Some of these circuits are shown below. The function \(S_{I}\), where \(I \subseteq [5]\), is defined as follows: \(S_{I}(x_{1}, x_{2}, x_{3}, x_{4}, x_{5})=[x_{1}+x_{2}+x_{3}+x_{4}+x_{5} \in I]\) (thus, \(S_{I}\) is symmetric).