Lower bounds for complexity of Boolean circuits of finite depth with arbitrary elements
Lower bounds for complexity of Boolean circuits of finite depth with arbitrary elements
复制标题
具有任意元素的有限深度布尔电路的复杂性下界
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
D. Cherukhin
中科院分区：
文献类型：
--
作者：
D. Cherukhin
摘要我们考虑了有限深度的功能元素，其元素是任何数量的参数的任意布尔函数。对于深度d≥2的电路是ω（nλd– 1（n））的形式。 log n）和ω（n log n）分别为d≥5函数λD– 1（n）是一个缓慢增加的功能。这些估计已在作者的早期研究中获得。
Abstract We consider circuits of functional elements of a finite depth whose elements are arbitrary Boolean functions of any number of arguments. We suggest a method of finding nonlinear lower bounds for complexity applicable, in particular, to the operator of cyclic convolution. The obtained lower bounds for the circuits of depth d ≥ 2 are of the form Ω(nλ d–1(n)). In particular, for d = 2, 3, 4 they are of the form Ω(n 3/2), Ω(n log n), and Ω(n log log n) respectively; for d ≥ 5 the function λ d–1(n) is a slowly increasing function. These lower bounds are the greatest known ones for all even d and for d = 3. For d = 2, 3, these estimates have been obtained in earlier studies of the author.