Geodesic
On the complexity of the realization of a linear function by formulas in finite Boolean bases
Diskretnaya Matematika, Tome 12 (2000) no. 1, pp. 135-144 
D. Yu. Cherukhin. On the complexity of the realization of a linear function by formulas in finite Boolean bases. Diskretnaya Matematika, Tome 12 (2000) no. 1, pp. 135-144. http://geodesic.mathdoc.fr/item/DM_2000_12_1_a10/
@article{DM_2000_12_1_a10,
     author = {D. Yu. Cherukhin},
     title = {On the complexity of the realization of a linear function by formulas in finite {Boolean} bases},
     journal = {Diskretnaya Matematika},
     pages = {135--144},
     year = {2000},
     volume = {12},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2000_12_1_a10/}
}
TY  - JOUR
AU  - D. Yu. Cherukhin
TI  - On the complexity of the realization of a linear function by formulas in finite Boolean bases
JO  - Diskretnaya Matematika
PY  - 2000
SP  - 135
EP  - 144
VL  - 12
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DM_2000_12_1_a10/
LA  - ru
ID  - DM_2000_12_1_a10
ER  - 
%0 Journal Article
%A D. Yu. Cherukhin
%T On the complexity of the realization of a linear function by formulas in finite Boolean bases
%J Diskretnaya Matematika
%D 2000
%P 135-144
%V 12
%N 1
%U http://geodesic.mathdoc.fr/item/DM_2000_12_1_a10/
%G ru
%F DM_2000_12_1_a10

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

We completely describe the set of bases over which the complexity of realization of the function $x_1\oplus\ldots\oplus x_n$ is of order $n$. For all bases not belonging to this set, we obtain the lower bound for the complexity of realization of the function $x_1\oplus\ldots\oplus x_n$, which is of the form $n^c$, where $c>1$ and $c$ does not depend on $n$. Basing on this bound for complexity, we give a more simple proof of existence of an infinite (descending) sequence of Boolean bases. The research was supported by the Russian Foundation for Basic Research, grant 99–01–01175, and also by FTP ‘Integration’, grant 473.

[1] Muchnik B. A., “Otsenka slozhnosti realizatsii lineinoi funktsii formulami v nekotorykh bazisakh”, Kibernetika, 1970, no. 4, 29–38 | Zbl

[2] Peryazev N. A., “Slozhnost predstavlenii bulevykh funktsii formulami v nemonolineinykh bazisakh”, Diskretnaya matematika i informatika, 1995, Irkutskii universitet, Irkutsk

[3] Stetsenko V. A., “O predplokhikh bazisakh v $P_2$”, Matematicheskie voprosy kibernetiki, 4 (1992), 139–177 | MR | Zbl

[4] Subbotovskaya B. A., “O realizatsii lineinykh funktsii formulami v bazise $\vee$, $\$, $\bar{}$”, Dokl. AN SSSR, 136:3 (1961), 553–555 | Zbl

[5] Subbotovskaya B. A., “O sravnenii bazisov pri realizatsii funktsii algebry logiki formulami”, Dokl. AN SSSR, 149:4 (1963), 784–787 | MR | Zbl

[6] Khrapchenko V. M., “O slozhnosti realizatsii lineinoi funktsii v klasse $\Pi$-skhem”, Matem. zametki, 9:1 (1971), 35–40 | Zbl

[7] Cherukhin D. Yu., “Ob odnoi beskonechnoi posledovatelnosti uluchshayuschikhsya bulevykh bazisov”, Diskretnyi analiz i issledovanie operatsii, 4:4 (1997), 79–95 | MR | Zbl

[8] Cherukhin D. Yu., “O predplokhikh bulevykh bazisakh”, Diskretnaya matematika, 11:2 (1999), 118–160 | MR | Zbl

[9] Yablonskii S. V., “Realizatsiya lineinoi funktsii v klasse $\Pi$-skhem”, Dokl. AN SSSR, 94:5 (1954), 805–806 | MR | Zbl