|
Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika, 2018, Number 3, Pages 60–64
(Mi vmumm35)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
Short notes
Generalization of complexity estimates for flat circuits realizing partial Boolean operators
G. V. Kalachev Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
Abstract:
In this paper we consider the Shannon function of plain circuit activity for class of partial Boolean operators with restrictions on the number of different operator values. It is proved that for the class of partial operators with $m$ outputs, domain of cardinality $d$, and the number of different values not exceeding $r$ the mean and maximal orders of activity are equal to $(\sqrt{d}+m\sqrt{r}/\log r)\sqrt{\log r}$ by the order.
Key words:
plain circuits, activity, potential, Shannon function, lower bounds, upper bounds, Boolean operators.
Received: 27.09.2017
Citation:
G. V. Kalachev, “Generalization of complexity estimates for flat circuits realizing partial Boolean operators”, Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2018, no. 3, 60–64; Moscow University Mathematics Bulletin, 73:3 (2018), 120–123
Linking options:
https://www.mathnet.ru/eng/vmumm35 https://www.mathnet.ru/eng/vmumm/y2018/i3/p60
|
|