Report Number: CS-TR-76-553
Institution: Stanford University, Department of Computer Science
Title: Complexity of monotone networks for computing conjunctions
Author: Tarjan, Robert Endre
Date: June 1976
Abstract: Let $F_1$, $F_2$,..., $F_m$ be a set of Boolean functions of the form $F_i$ = $\wedge$ {x$\in X_i$}, where $\wedge$ denotes conjunction and each $X_i$ is a subset of a set X of n Boolean variables. We study the size of monotone Boolean networks for computing such sets of functions. We exhibit anomalous sets of conujunctions whose smallest monotone networks contain disjunctions. We show that if |$F_i$| is sufficiently small for all i, such anomalies cannot happen. We exhibit sets of m conjunctions in n unknowns which require $c_2$m$\alpha$(m,n) binary conjunctions, where $\alpha$(m,n) is a very slowly growing function related to a functional inverse of Ackermann's function. This class of examples shows that an algorithm given in [STAN-CS-75-512] for computing functions defined on paths in trees is optimum to within a constant factor.
http://i.stanford.edu/pub/cstr/reports/cs/tr/76/553/CS-TR-76-553.pdf