Complexity of monotone networks for computing conjunctions

Research output: Contribution to journalArticle

21 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)121-133
Number of pages13
JournalAnnals of Discrete Mathematics
Volume2
Issue numberC
DOIs
StatePublished - Jan 1 1978
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Complexity of monotone networks for computing conjunctions'. Together they form a unique fingerprint.

  • Cite this