A new lower bound on the monotone network complexity of Boolean sums
A new lower bound on the monotone network complexity of Boolean sums
复制标题
布尔和单调网络复杂度的新下界
作者：
I. Wegener
summaryneciporuk [3]，lamagna/savage [1]和tarjan [6]确定了一组布尔总和的单调网络复杂性，如果每个总和最多具有一个共同的一个变量。通过这种结果，他们可以明确定义一组N Boolean总和，该总和取决于N变量以及其单调复杂性为N3/2阶。在本文的主要定理中，我们证明了布尔总和的单调网络复杂性更一般的下限。对于许多布尔，我们的下限是第一个非平凡的下限。另一方面，我们可以证明主要定理产生的最佳下限是上面引用的N3/2-bound。为了证明，我们使用的是假设免费提供某些功能的技术技巧。
SummaryNeciporuk [3], Lamagna/Savage [1] and Tarjan [6] determined the monotone network complexity of a set of Boolean sums if each two sums have at most one variable in common. By this result they could define explicitely a set of n Boolean sums which depend on n variables and whose monotone complexity is of order n3/2. In the main theorem of this paper we prove a more general lower bound on the monotone network complexity of Boolean sums. Our lower bound is for many Boolean sums the first nontrivial lower bound. On the other side we can prove that the best lower bound which the main theorem yields is the n3/2-bound cited above. For the proof we use the technical trick of assuming that certain functions are given for free.