The circuit depth of symmetric boolean functions

摘要

Let Sn be the set of symmetric Boolean functions of n arguments. The depth of every NAND circuit which evaluates a nonconstant function in Sn is at least 2 log2n − α, where α = 2 log23 − 1 ≅ 2 · 17. For the basis {NAND, →} a lower bound of 1 · 44log2n − β is obtained, where β = 3 − logφ 512 ≅ 1 · 328. [φ = (1 + 512)/2 is the golden (Fibonacci) ratio.] The coefficient 1 · 44 is precisely given by logφ2. These results follow from general criteria relating circuit depth to the size of implicants. For certain symmetric functions, these lower bounds could not be derived from corresponding bounds on formula size. All but eight of the functions in Sn require unate formulae of size Ω(n · log2n). Each of the eight exceptions has a formula of size at most 2n.