|
Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika, 2016, Number 2, Pages 51–52
(Mi vmumm138)
|
|
|
|
Short notes
Complexity of linear and majority functions in the basis of antichain functions
O. V. Podolskaya Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
Abstract:
The complexity circuits of Boolean functions is studied in a basis consisting of all characteristic functions of antichains over the Boolean cube. It is established that the circuit complexity of an $n$-variable parity function is $\left\lfloor \frac{n+1}{2}\right\rfloor$ and the complexity of its negation equals the complexity of the $n$-variable majority function which is $\left\lceil \frac{n+1}{2} \right\rceil$.
Key words:
antichain function, circuit complexity, parity function, majority function.
Received: 25.05.2015
Citation:
O. V. Podolskaya, “Complexity of linear and majority functions in the basis of antichain functions”, Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2016, no. 2, 51–52; Moscow University Mathematics Bulletin, 71:2 (2016), 82–83
Linking options:
https://www.mathnet.ru/eng/vmumm138 https://www.mathnet.ru/eng/vmumm/y2016/i2/p51
|
Statistics & downloads: |
Abstract page: | 120 | Full-text PDF : | 34 | References: | 13 |
|