Geodesic
Relation between two measures of the computation complexity for systems of monomials
Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 4 (2009), pp. 8-13

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{VMUMM_2009_4_a1,
     author = {V. V. Kochergin},
     title = {Relation between two measures of the computation complexity for systems of monomials},
     journal = {Vestnik Moskovskogo universiteta. Matematika, mehanika},
     pages = {8--13},
     publisher = {mathdoc},
     number = {4},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMUMM_2009_4_a1/}
}
TY  - JOUR
AU  - V. V. Kochergin
TI  - Relation between two measures of the computation complexity for systems of monomials
JO  - Vestnik Moskovskogo universiteta. Matematika, mehanika
PY  - 2009
SP  - 8
EP  - 13
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VMUMM_2009_4_a1/
LA  - ru
ID  - VMUMM_2009_4_a1
ER  - 
%0 Journal Article
%A V. V. Kochergin
%T Relation between two measures of the computation complexity for systems of monomials
%J Vestnik Moskovskogo universiteta. Matematika, mehanika
%D 2009
%P 8-13
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VMUMM_2009_4_a1/
%G ru
%F VMUMM_2009_4_a1
V. V. Kochergin. Relation between two measures of the computation complexity for systems of monomials. Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 4 (2009), pp. 8-13. http://geodesic.mathdoc.fr/item/VMUMM_2009_4_a1/