TY - JOUR

T1 - Complexity of monotone networks for computing conjunctions

AU - Tarjan, Robert Endre

N1 - Funding Information:
* Research partially supported by National Science Foundation grant MCS 75-22870 and Naval Research contract N00014-76-C-0688.

PY - 1978/1/1

Y1 - 1978/1/1

N2 - Let F1, F2…, Fm be a set of Boolean functions of the form F1 = ^{x E X1}, where ^ denotes conjuction and each X1, 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 conjunctions whose smallest monotone networks contain disjunctions. We show that if |F|, is sufficiently small for all i, such anomalies cannot happen. We exhibit sets of m conjuctions in n unknowns which require c2ma(m, n) binary conjunctions, where α(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 [12] for computing functions defined on paths in trees is optimum to within a constant factor.

AB - Let F1, F2…, Fm be a set of Boolean functions of the form F1 = ^{x E X1}, where ^ denotes conjuction and each X1, 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 conjunctions whose smallest monotone networks contain disjunctions. We show that if |F|, is sufficiently small for all i, such anomalies cannot happen. We exhibit sets of m conjuctions in n unknowns which require c2ma(m, n) binary conjunctions, where α(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 [12] for computing functions defined on paths in trees is optimum to within a constant factor.

UR - http://www.scopus.com/inward/record.url?scp=0343695884&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0343695884&partnerID=8YFLogxK

U2 - 10.1016/S0167-5060(08)70326-1

DO - 10.1016/S0167-5060(08)70326-1

M3 - Article

AN - SCOPUS:0343695884

VL - 2

SP - 121

EP - 133

JO - Annals of Discrete Mathematics

JF - Annals of Discrete Mathematics

SN - 0167-5060

IS - C

ER -