A note on the circuit complexity of PP
In this short note, we show that for any integer k, there are languages in the complexity class PP that do not have Boolean circuits of size n(k). (c) 2005 Elsevier B.V. All rights reserved.
complexity classes computational complexity circuit lower bounds