Geodesic
On bounds for complexity of circuits of multi-input functional elements
Diskretnaya Matematika, Tome 22 (2010) no. 1, pp. 50-57.

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper we suggest a method to find lower bounds for complexity of circuits of functional elements. The essence of the method consists of replacing the initial, maybe quite complex, basis containing multi-input elements by a more simple basis, say, of two-input elements, with subsequent use of known lower bounds for complexity of circuits in the simple basis. The efficiency of this method is illustrated on particular examples of finding the asymptotics and even precise values of complexities of realisation of special Boolean functions, monotone Boolean functions and functions with small number of ones. 
@article{DM_2010_22_1_a3,
     author = {N. P. Redkin},
     title = {On bounds for complexity of circuits of multi-input functional elements},
     journal = {Diskretnaya Matematika},
     pages = {50--57},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2010_22_1_a3/}
}
TY  - JOUR
AU  - N. P. Redkin
TI  - On bounds for complexity of circuits of multi-input functional elements
JO  - Diskretnaya Matematika
PY  - 2010
SP  - 50
EP  - 57
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2010_22_1_a3/
LA  - ru
ID  - DM_2010_22_1_a3
ER  - 
%0 Journal Article
%A N. P. Redkin
%T On bounds for complexity of circuits of multi-input functional elements
%J Diskretnaya Matematika
%D 2010
%P 50-57
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2010_22_1_a3/
%G ru
%F DM_2010_22_1_a3
N. P. Redkin. On bounds for complexity of circuits of multi-input functional elements. Diskretnaya Matematika, Tome 22 (2010) no. 1, pp. 50-57. http://geodesic.mathdoc.fr/item/DM_2010_22_1_a3/

[1] Lupanov O. B., Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo MGU, Moskva, 1984

[2] Redkin N. P., “Dokazatelstvo minimalnosti nekotorykh skhem iz funktsionalnykh elementov”, Problemy kibernetiki, 23, 1970, 83–101 | MR

[3] Grinchuk M. I., “O monotonnoi slozhnosti porogovykh funktsii”, Metody diskretnogo analiza v teorii grafov i slozhnosti, 52, 1992, 41–48 | MR | Zbl

[4] Finikov B. I., “Ob odnom semeistve klassov funktsii algebry logiki i ikh realizatsii v klassa $\Pi$-skhem”, Dokl. AN SSSR, 115:2 (1957), 247–248 | MR | Zbl

[5] Lupanov O. B., “Ob odnom podkhode k sintezu upravlyayuschikh sistem – printsipe lokalnogo kodirovaniya”, Problemy kibernetiki, 14, 1965, 31–110 | MR | Zbl

[6] Redkin N. P., “O slozhnosti bulevykh funktsii s malym chislom edinits”, Diskretnaya matematika, 16:4 (2004), 20–31 | MR | Zbl

[7] Redkin N. P., Diskretnaya matematika, TsPI pri mekh.-mat. f-te MGU, Moskva, 2007