Geodesic
A simple proof for the upper bound of the computational complexity of three monomials in three variables
Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 2 (2019), pp. 3-8 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The problem of the minimal number of multiplication operations sufficient for the joint computing of three monomials in three variables is considered. For this problem, we propose a simple proof of the upper bound asymptotically equal to the lower bound. The known proof of a similar bound contains more than 60 pages. 
@article{VMUMM_2019_2_a0,
     author = {V. V. Kochergin},
     title = {A simple proof for the upper bound of the computational complexity of three monomials in three variables},
     journal = {Vestnik Moskovskogo universiteta. Matematika, mehanika},
     pages = {3--8},
     year = {2019},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMUMM_2019_2_a0/}
}
TY  - JOUR
AU  - V. V. Kochergin
TI  - A simple proof for the upper bound of the computational complexity of three monomials in three variables
JO  - Vestnik Moskovskogo universiteta. Matematika, mehanika
PY  - 2019
SP  - 3
EP  - 8
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VMUMM_2019_2_a0/
LA  - ru
ID  - VMUMM_2019_2_a0
ER  - 
%0 Journal Article
%A V. V. Kochergin
%T A simple proof for the upper bound of the computational complexity of three monomials in three variables
%J Vestnik Moskovskogo universiteta. Matematika, mehanika
%D 2019
%P 3-8
%N 2
%U http://geodesic.mathdoc.fr/item/VMUMM_2019_2_a0/
%G ru
%F VMUMM_2019_2_a0
V. V. Kochergin. A simple proof for the upper bound of the computational complexity of three monomials in three variables. Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 2 (2019), pp. 3-8. http://geodesic.mathdoc.fr/item/VMUMM_2019_2_a0/

[1] Knut D. E., Iskusstvo programmirovaniya dlya EVM, v. 2, 1-e izd., Mir, M., 1977

[2] Pippenger N., “On evaluation of powers and monomials”, SIAM J. Comput., 9:2 (1980), 230–250 | DOI | MR | Zbl

[3] Kochergin V. V., “O zadachakh Bellmana i Knuta i ikh obobscheniyakh”, Fund. i prikl. matem., 20:6 (2015), 159–189

[4] Kochergin V. V., “Ob asimptotike slozhnosti additivnykh vychislenii sistem tselochislennykh lineinykh form”, Diskretnyi analiz i issledovanie operatsii. Ser. 1, 13:2 (2006), 38–58 | Zbl

[5] Kochergin V. V., “O slozhnosti additivnykh vychislenii, ispolzuyuschikh tolko operatsii vychitaniya”, Tr. VIII Mezhdunar. konf. “Diskretnye modeli v teorii upravlyayuschikh sistem” (Moskva, 6–9 aprelya 2009 g.), MAKS Press, M., 2009, 174–179

[6] Kochergin V. V., “Ob odnom sootnoshenii dvukh mer slozhnosti vychisleniya sistem odnochlenov”, Vestn. Mosk. un-ta. Matem. Mekhan., 2009, no. 4, 8–13 | Zbl

[7] Kochergin V. V., “O slozhnosti vychisleniya sistemy iz trekh odnochlenov ot trekh peremennykh”, Matematicheskie voprosy kibernetiki, 15, Fizmatlit, M., 2006, 79–155

[8] Lupanov O. B., “O sinteze nekotorykh klassov upravlyayuschikh sistem”, Problemy kibernetiki, 10, Fizmatgiz, M., 1963, 63–97

[9] Brauer A., “On addition chains”, Bull. Amer. Math. Soc., 45 (1939), 736–739 | DOI | MR

[10] Kochergin V. V., “O slozhnosti vychisleniya sistem odnochlenov ot dvukh peremennykh”, Tr. VII Mezhdunar. konf. “Diskretnye modeli v teorii upravlyayuschikh sistem”, MAKS Press, M., 2006, 185–190