Complexity classes defined in terms of Boolean circuits include AC0, AC, TC0 and NC. ==History== Circuit complexity goes back to Shannon (1949), who proved that almost all Boolean functions on n variables require circuits of size Θ(2n/n). Despite this fact, complexity theorists have not been able to prove superpolynomial circuit lower bounds for ...