Complexity of Linear and Majority Functions in the Basis of Antichain Functions / O. V. Podolskaya. // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2016. № 2. P. 51-52 [Moscow Univ. Math. Bulletin. Vol. 72, N 2, 2017. P. 82-83].
The complexity of realization of Boolean functions by circuits of functional elements
in the basis consisting of all characteristic functions of antichains over a Boolean cube is studied.
It is proved that the complexity of realization of an n-variable parity function is
Key words: antichain function, circuit complexity, parity function, majority function.