!)arity, Circuits, and the Polynomial.l'iole Hierarchy
Merrick L. Furst, James B. Saxe, J Michael Sipser · 1981
cuit COIJlputes f on inputs of size i, the depth of each circuit is bounded by a constant k, and the nUInber of gates in Ci, is at most g(i). Bounded-depth circuits arise naturally, modeling for example the program logic ar rays (PLA's) of VLSI {MO}. Lupanov (L] studied bounded-depth circuits in 1961 and proved that depth 2 parity circuits nlust have exponential size. A consequence is that parity, expressed in either disjunctive or conjunctive normal form, requires exponential space [8]. We show that parity cannot be .computed in any bounded depth with polynomial-size circuits. As a result we also prove that bounded-depth circuits for multiplying integers or taking the transitive closure of graphs require more than a polynomial number of gates. With respect to PLA's this proves that multi plication and transitive closure cannot be computed with PLA's of polynomial size. Further exploring the computational power of bounded-depth circuits we prove that an infinite version of parity cannot be com puted by a countable circuit having bounded depth. Whether there exists an oracle A such that PSPAC~ properly contains every E[,A is an open question. We show· a connection between this prob lem and the problem of determining exponential lower bounds on the size of bounded-depth circuits. In par ticular, we conjecture that the parity function cannot