Lesson 3

The previous theorem proves the existence of a function with high circuit complexity non-constructively: it does not give explicit examples of functions with high circuit complexity and does not rule out the possibility that various functions of practical interest (such as, for example, the function of factoring a number) can be computed by small circuits.