Relation Between Two Measures of the Computation Complexity for Systems of Monomials

摘要

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.