Circuit complexity

Summary

Circuit complexity measures how hard a Boolean function is by the size or depth of the smallest Boolean circuit that computes it. A language is studied through the family of circuits that decide it on each input length. Lower bounds on circuit size are a route to separating complexity classes, since every problem in P has circuits of polynomial size. Strong lower bounds are known for restricted circuits, such as constant-depth and monotone circuits, but not for general ones.