Explicit lower bound of 4.5n - o(n) for boolena circuits
Explicit lower bound of 4.5n - o(n) for boolena circuits
复制标题
布尔电路的显式下限 4.5n - o(n)
DOI：
10.1145/380752.380832
复制
发表时间：
2001
影响因子：
0.9
通讯作者：
R. Raz
中科院分区：
文献类型：
--
作者：
Oded Lachish;R. Raz
我们在 U_2 的基础上证明了显式布尔函数（即在确定性多项式时间内可构造的函数）的电路复杂度的下限 4.5n - o(n)</italic>。也就是说，我们在 <italic>{and,or,not}</italic> 的基础上获得了计算某个布尔函数所需的 <italic>{and,or}</italic> 门数量的 <italic>4.5n - o(n)</italic> 下界（其中 <italic>not</italic> 门不计算在内）。我们的证明基于布尔函数的一个新组合属性，称为“强二依赖”，这个概念本身可能很有趣。我们的下界适用于任何强二元相关布尔函数。
We prove a lower bound of <italic>4.5n - o(n)</italic> for the circuit complexity of an explicit Boolean function (that is, a function constructible in deterministic polynomial time), over the basis <italic>U_2</italic>. That is, we obtain a lower bound of <italic>4.5n - o(n)</italic> for the number of <italic>{and,or}</italic> gates needed to compute a certain Boolean function, over the basis <italic>{and,or,not}</italic> (where the <italic>not</italic> gates are not counted). Our proof is based on a new combinatorial property of Boolean functions, called <italic>Strongly-Two-Dependence</italic>, a notion that may be interesting in its own right. Our lower bound applies to any Strongly-Two-Dependent Boolean function.