非表示:
キーワード:
-
要旨:
Summary Neciporuk, Lamagna/Savage and Tarjan determined the monotone network
complexity of a set of Boolean sums if any two sums have at most one variable
in common. Wegener then solved the case that any two sums have at most k
variables in common. We extend his methods and results and consider the case
that any set of h +1 distinct sums have at most k variables in common. We use
our general results to explicitly construct a set of n Boolean sums over n
variables whose monotone complexity is of order n 5/3. The best previously
known bound was of order n 3/2. Related results were obtained independently by
Pippenger.
This paper was presented at the MFCS 79 Symposium, Olomouc, Sept. 79
