Circuit complexity of symmetric Boolean functions in antichain basis
Diskretnaya Matematika, Tome 27 (2015) no. 3, pp. 95-107
Voir la notice de l'article provenant de la source Math-Net.Ru
We study the circuit complexity of Boolean functions in an infinite basis consisting of all characteristic functions of antichains over the Boolean cube. For an arbitrary symmetric function we obtain the exact value of its circuit complexity in this basis. In particular, we prove that the circuit complexities of the parity function and the majority function of $n$ variables for all integers $n\geqslant1$ in this basis are $\lfloor \frac{n+1}{2} \rfloor$ and $\left\lfloor \frac{n}{2} \right \rfloor +1$ respectively. For the maximum circuit complexity of $n$-variable Boolean functions in this basis, we show that its order of growth is equal to $n.$ \hspace{12cm} \linebreak The research is supported by the Russian Foundation for Basic Research, project 14–01–00598.
Keywords:
Boolean circuit complexity, antichain functions, Boolean circuits, symmetric Boolean functions, the Shannon function.
@article{DM_2015_27_3_a6,
author = {Olga V. Podolskaya},
title = {Circuit complexity of symmetric {Boolean} functions in antichain basis},
journal = {Diskretnaya Matematika},
pages = {95--107},
publisher = {mathdoc},
volume = {27},
number = {3},
year = {2015},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/DM_2015_27_3_a6/}
}
Olga V. Podolskaya. Circuit complexity of symmetric Boolean functions in antichain basis. Diskretnaya Matematika, Tome 27 (2015) no. 3, pp. 95-107. http://geodesic.mathdoc.fr/item/DM_2015_27_3_a6/