A 4n Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions
A 4n Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions
复制标题
基于单二进布尔函数的某些对称布尔函数组合复杂度的4n下界
DOI：
10.1137/0220032
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
Uri Zwick
中科院分区：
文献类型：
--
作者：
Uri Zwick
A simple, and easy-to-check, property of a symmetric boolean function is shown to imply a $4n - O(1)$ lower bound on the circuit complexity of the function over $U_2 = B_2 - \{ \oplus , \equiv \}$, the basis of unate dyadic boolean functions. Among the functions to which this lower bound applies are the modular functions ${\operatorname{MOD}}_k (n)$ for any fixed $k \geqq 3$ (${\operatorname{MOD}}_k (n)$ is the function which returns 1 if and only if $(\sum x_i )\bmod k = 0$). Finally, a $5n$ upper bound is obtained on the circuit complexity over $U_2 $ of the function ${\operatorname{MOD}}_4 (n)$.
A simple, and easy-to-check, property of a symmetric boolean function is shown to imply a $4n - O(1)$ lower bound on the circuit complexity of the function over $U_2 = B_2 - \{ \oplus , \equiv \}$, the basis of unate dyadic boolean functions. Among the functions to which this lower bound applies are the modular functions ${\operatorname{MOD}}_k (n)$ for any fixed $k \geqq 3$ (${\operatorname{MOD}}_k (n)$ is the function which returns 1 if and only if $(\sum x_i )\bmod k = 0$). Finally, a $5n$ upper bound is obtained on the circuit complexity over $U_2 $ of the function ${\operatorname{MOD}}_4 (n)$.