Relation Between Two Measures of the Computation Complexity for Systems of Monomials / V.V. Kochergin // Vestn. Mosk. Univ., Matem. Mekhan. 2009. № 4. P. 8-13 [Moscow Univ. Math. Bulletin. Vol. 64, No 4, 2009. 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 compute the system starting from variables). An example of a sequence of matrices (systems of monomials, respectively) is also given so that the usage of inverse values of variables (in addition to the variables themselves) makes the complexity asymptotically two times less.
Key words: addition chain, computation complexity of system of monomials.