RUS  ENG
Full version
JOURNALS // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika // Archive

Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2009 Number 4, Pages 8–13 (Mi vmumm883)

This article is cited in 4 papers

Mathematics

Relation between two measures of the computation complexity for systems of monomials

V. V. Kochergin

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: 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.

UDC: 519.71

Received: 19.11.2008



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025