Lesson 7

Circuits are important both from theoretical and practical points of view.

• Practice.  A Boolean circuit is the simplest mathematical model of a microchip. When you write \(\texttt{x+y}\) in a programming language, somewhere deep inside the processor a large circuit is adding bits, producing sum bits and carry bits, over and over again. Designing small and fast circuits is a real engineering task.
  Engineers depict the Half Adder and Full Adder circuits (we considered them above) a little differently.
  

  

  
  Also, one can see a neural network as a circuit: its values are usually real numbers, its gates perform arithmetic operations, and its parameters are learned from data. After training is finished, evaluating a fixed neural network on a fixed input is just a large directed acyclic computation: simple local operations are applied layer by layer until the output is produced.
  In practice, engineers optimize not only size but also many other parameters: depth, total area, and others.


• Theory.  Boolean circuits are one of the cleanest computation models. They have no loops and no conditional branches; all values are bits; the only operations are tiny Boolean gates. This simplicity makes circuits convenient for proofs.
  At the same time, circuits are very powerful. Roughly speaking, if a computational task can be quickly solved on a computer, then for each input length \(n\) there exist small circuits that solve inputs of length \(n\). (Here “for each \(n\)” is important: circuits form a non-uniform model, unlike algorithms.)
  The main open problem in this field is to prove that for some explicitly given Boolean function, there are no circuits of polynomial size. This is the problem of whether the classes P and NP are equal, and solving it carries a one-million-dollar prize from the Clay Mathematics Institute.