|
Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika, 2016, Number 3, Pages 53–57
(Mi vmumm155)
|
|
|
|
This article is cited in 3 scientific papers (total in 4 papers)
Short notes
Complexity and depth of formulas for symmetric Boolean functions
I. S. Sergeev Research Institute "Kvant", Moscow
Abstract:
A new approach for implementation of the counting function for a Boolean set is proposed. The approach is based on approximate calculation of sums. Using this approach, new upper bounds for the size and depth of symmetric functions over the basis $B_2$ of all dyadic functions and over the standard basis $B_0 =\{ \wedge, \vee,\overline{\phantom a} \}$ were non-constructively obtained. In particular, the depth of multiplication of $n-$bit binary numbers is asymptotically estimated from above by $4.02\log_2n$ relative to the basis $B_2$ and by $5.14\log_2n$ relative to the basis $B_0$.
Key words:
Boolean formulae, formula size, depth, symmetric Boolean functions, multiplication.
Received: 30.09.2015
Citation:
I. S. Sergeev, “Complexity and depth of formulas for symmetric Boolean functions”, Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2016, no. 3, 53–57; Moscow University Mathematics Bulletin, 71:3 (2016), 127–130
Linking options:
https://www.mathnet.ru/eng/vmumm155 https://www.mathnet.ru/eng/vmumm/y2016/i3/p53
|
Statistics & downloads: |
Abstract page: | 169 | Full-text PDF : | 48 | References: | 25 |
|