Geodesic
On the complexity of Boolean functions with a small number of ones
Diskretnaya Matematika, Tome 16 (2004) no. 4, pp. 20-31 
N. P. Red'kin. On the complexity of Boolean functions with a small number of ones. Diskretnaya Matematika, Tome 16 (2004) no. 4, pp. 20-31. http://geodesic.mathdoc.fr/item/DM_2004_16_4_a2/
@article{DM_2004_16_4_a2,
     author = {N. P. Red'kin},
     title = {On the complexity of {Boolean} functions with a small number of ones},
     journal = {Diskretnaya Matematika},
     pages = {20--31},
     year = {2004},
     volume = {16},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2004_16_4_a2/}
}
TY  - JOUR
AU  - N. P. Red'kin
TI  - On the complexity of Boolean functions with a small number of ones
JO  - Diskretnaya Matematika
PY  - 2004
SP  - 20
EP  - 31
VL  - 16
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DM_2004_16_4_a2/
LA  - ru
ID  - DM_2004_16_4_a2
ER  - 
%0 Journal Article
%A N. P. Red'kin
%T On the complexity of Boolean functions with a small number of ones
%J Diskretnaya Matematika
%D 2004
%P 20-31
%V 16
%N 4
%U http://geodesic.mathdoc.fr/item/DM_2004_16_4_a2/
%G ru
%F DM_2004_16_4_a2

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

We consider the class of Boolean functions $F_{n,k}$ consisting of all functions in $n$ variables such that each of them takes value one exactly for $k$ tuples of variables. We obtain linear in $n$ estimates of the complexity of realisation of functions in $F_{n,k}$ by circuits of functional elements over the basis containing all Boolean functions in two variables except the linear functions $x \oplus y$ and $x\oplus y\oplus 1$. It follows from these estimates that for small $k$, for example, for $k\ln n$, the well-known Finikov method provides asymptotically minimal circuits for all functions of $F_{n,k}$. In some cases, the known lower bounds for complexity of circuits give a possibility to prove the minimality of the corresponding circuits. The research was supported by the Russian Foundation for Basic Research, grant 02–01–00985, by the program of President of Russian Federation for support of leading scientific schools, grant 1807.2003.1, and by the program ‘Universities of Russia.’

[1] Shennon K. E., Raboty po teorii informatsii i kibernetike, IL, Moskva, 1963

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

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

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

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

[6] Redkin N. P., “O minimalnoi realizatsii dvoichnogo summatora”, Problemy kibernetiki, 38 (1981), 181–216 | MR

[7] Redkin N. P., “Asimptoticheski minimalnye samokorrektiruyuschie skhemy dlya odnoi posledovatelnosti bulevykh funktsii”, Diskretnyi analiz i issledovanie operatsii, 3:2 (1996), 62–79 | MR

[8] Redkin N. P., “O polnykh proveryayuschikh testakh dlya skhem iz funktsionalnykh elementov”, Matem. voprosy kibern., 2 (1989), 198–222 | MR

[9] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Nauka, Moskva, 1986 | MR