Geodesic
On the asymptotic behavior of Shannon-type functions characterizing the computing complexity of systems of monomials
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 162 (2020) no. 3, pp. 300-310 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

In this paper, we examined the computational complexity of systems of monomials for some models that allow multiple use of intermediate results, such as composition circuits and multiplication circuits. For these models, we studied Shannon-type functions that characterize the maximum computational complexity of systems of monomials with exponents not exceeding the corresponding elements of a given matrix $A$. We found that for composition circuits, under the condition of unlimited growth of the maximum of matrix elements, this function grows asymptotically as the binary logarithm of the maximum absolute value (without regard to the sign) of the term from the determinant of the matrix $A.$ Using generalized circuits as an auxiliary model, we transferred this result (under some restrictions) to the model of multiplication circuits.
Keywords: set of monomials, computation complexity, circuit complexity, Shannon function. 
@article{UZKU_2020_162_3_a4,
     author = {S. A. Korneev},
     title = {On the asymptotic behavior of {Shannon-type} functions characterizing the computing complexity of systems of monomials},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {300--310},
     year = {2020},
     volume = {162},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2020_162_3_a4/}
}
TY  - JOUR
AU  - S. A. Korneev
TI  - On the asymptotic behavior of Shannon-type functions characterizing the computing complexity of systems of monomials
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2020
SP  - 300
EP  - 310
VL  - 162
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/UZKU_2020_162_3_a4/
LA  - ru
ID  - UZKU_2020_162_3_a4
ER  - 
%0 Journal Article
%A S. A. Korneev
%T On the asymptotic behavior of Shannon-type functions characterizing the computing complexity of systems of monomials
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2020
%P 300-310
%V 162
%N 3
%U http://geodesic.mathdoc.fr/item/UZKU_2020_162_3_a4/
%G ru
%F UZKU_2020_162_3_a4
S. A. Korneev. On the asymptotic behavior of Shannon-type functions characterizing the computing complexity of systems of monomials. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 162 (2020) no. 3, pp. 300-310. http://geodesic.mathdoc.fr/item/UZKU_2020_162_3_a4/

[1] Kochergin V. V., “On the complexity of joint calculation of three monomials of three variables”, Mat. Vopr. Kibern., 15, 2006, 79–154 (In Russian)

[2] Shirshov A. I., “Some algorithmic problems for Lie algebras”, Sib. Mat. Zh., 3:2 (1962), 292–296 (In Russian) | MR | Zbl

[3] Merekin Yu.V., “On the generation of words using the composition operation”, Diskretn. Anal. Issled. Oper. Ser. 1, 10:4 (2003), 70–78 (In Russian) | MR | Zbl

[4] Trusevich E. N., “Complexity of certain systems of monomials in calculation by composition circuits”, Moscow Univ. Math. Bull., 69:5 (2014), 193–197 | DOI | MR | Zbl

[5] Korneev S. A., “On the complexity of system of two monomials realization by composition circuits”, Diskretn. Mat., 32:2 (2020), 15–31 (In Russian) | DOI

[6] Kochergin V. V., R. Bellman and D. Knuth's Problems and Their Generalizations (Complexity of Additive Calculations), Palmarium Acad. Publ., Saarbrucken, 2012, 396 pp. (In Russian)