The Permanent Requires Large Uniform Threshold Circuits.
Eric Allender · 1999
A recent paper by Caussinus, McKenzie, Th'erien, and Vollmer [CMTV96] shows that there are problems in the counting hierarchy that require superpolynomial-size uniform TC 0 circuits. The proof in [CMTV96] uses "leaf languages" as a tool in obtaining their separations, and their proof does not immediately yield larger lower bounds for the complexity of these problems, and it also does not yield a lower bound for any particular problem at any fixed level of the counting hierarchy. (It only shows that hard problems must exist at some level.) In this paper, we give a simple direct proof, showing that any problem that is hard for the complexity class C=P requires more than size T (n), if for all k, T (k) (n) = o(2 n ). Thus, in particular, the permanent, and any problem hard for PP or #P require circuits of this size. Related and somewhat weaker lower bounds are also presented, extending the theorem of [CMTV96] showing that ACC 0 is properly contained in ModPH. 1 Introduction 1.1...