Geodesic
Multilevel representation and complexity of circuits of unbounded fan-in gates
Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 3 (2020), pp. 42-46 
I. S. Sergeev. Multilevel representation and complexity of circuits of unbounded fan-in gates. Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 3 (2020), pp. 42-46. http://geodesic.mathdoc.fr/item/VMUMM_2020_3_a5/
@article{VMUMM_2020_3_a5,
     author = {I. S. Sergeev},
     title = {Multilevel representation and complexity of circuits of unbounded fan-in gates},
     journal = {Vestnik Moskovskogo universiteta. Matematika, mehanika},
     pages = {42--46},
     year = {2020},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMUMM_2020_3_a5/}
}
TY  - JOUR
AU  - I. S. Sergeev
TI  - Multilevel representation and complexity of circuits of unbounded fan-in gates
JO  - Vestnik Moskovskogo universiteta. Matematika, mehanika
PY  - 2020
SP  - 42
EP  - 46
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VMUMM_2020_3_a5/
LA  - ru
ID  - VMUMM_2020_3_a5
ER  - 
%0 Journal Article
%A I. S. Sergeev
%T Multilevel representation and complexity of circuits of unbounded fan-in gates
%J Vestnik Moskovskogo universiteta. Matematika, mehanika
%D 2020
%P 42-46
%N 3
%U http://geodesic.mathdoc.fr/item/VMUMM_2020_3_a5/
%G ru
%F VMUMM_2020_3_a5

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

A new simpler proof of the asymptotic $C(n)\sim\sqrt2\cdot2^{n/2}$ of the Shannon function of the circuit complexity over the basis of multi-input generalized conjunctions is obtained.

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

[2] Markov A. A., “Ob inversionnoi slozhnosti sistem funktsii”, Dokl. AN SSSR, 116:6 (1957), 917–919 | Zbl

[3] Nechiporuk E. I., “O slozhnosti skhem v nekotorykh bazisakh, soderzhaschikh netrivialnye elementy s nulevymi vesami”, Problemy kibernetiki, 8, Fizmatlit, M., 1962, 123–160 | Zbl

[4] Sergeev I. S., “O slozhnosti skhem i formul ogranichennoi glubiny nad bazisom iz mnogovkhodovykh elementov”, Diskretn. matem., 30:2 (2018), 120–137

[5] Kartecu F., Vvedenie v konechnye geometrii, Mir, M., 1980