Lesson 1

Above, we proved that there are many functions in \(B_{n}\) with exponential circuit complexity. However, the proof was non-constructive. In particular, we did not provide a single example of an explicit complex function. (By explicit, we generally mean a function from the class NP.) For such functions, to this day, we can only prove weak linear lower bounds: approximately \(3n\) for circuits over the \(B_{2}\) basis, and \(5n\) for the \(U_{2}\) basis.