Relation between two measures of the computation complexity for systems of monomials / V. V. Kochergin. // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2009. № 4. P. 8-13 [Moscow Univ. Math. Bulletin. Vol. 72, N 2, 2017. P. 144-149].

For a class of matrices defining exponents of variables in a system of monomials, a nontrivial lower bound of complexity is found (where the complexity is defined as the minimum number of multiplications required to calculate the system starting from variables). An example of a sequence of matrices (system of monomials, respectively) is also given so that the usage of inverse values of variables (in addition to the variables themselves) makes the complexity asymptotycally two times less.

Key words: addition chain, computation complexity of system of monomials.