Geodesic
Complexity of certain systems of monomials in calculation by composition circuits
Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 5 (2014), pp. 18-22

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

In this paper we study the circuit complexity of monomials set computation. In the model considered here the complexity means the minimal number of composition operations sufficient for calculation of the system by its variables. It is established that the considered complexity measure can be much less than known complexity measures corresponding to models admitting, for example, either multiplication operation only, or multiplication and division operations, or multiplication operation with possibility to use inverse variables. However, this feature of a significant “computation strength” is not universal, which is confimed by an appropatiate example. Furthermore, for a system containing two monomials of two variables we obtained an exact complexity value. We also established that duality reasons do not work (or work poorly) in calculations with the use of composition operation. 
@article{VMUMM_2014_5_a2,
     author = {E. N. Trusevich},
     title = {Complexity of certain systems of monomials in calculation by composition circuits},
     journal = {Vestnik Moskovskogo universiteta. Matematika, mehanika},
     pages = {18--22},
     publisher = {mathdoc},
     number = {5},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMUMM_2014_5_a2/}
}
TY  - JOUR
AU  - E. N. Trusevich
TI  - Complexity of certain systems of monomials in calculation by composition circuits
JO  - Vestnik Moskovskogo universiteta. Matematika, mehanika
PY  - 2014
SP  - 18
EP  - 22
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VMUMM_2014_5_a2/
LA  - ru
ID  - VMUMM_2014_5_a2
ER  - 
%0 Journal Article
%A E. N. Trusevich
%T Complexity of certain systems of monomials in calculation by composition circuits
%J Vestnik Moskovskogo universiteta. Matematika, mehanika
%D 2014
%P 18-22
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VMUMM_2014_5_a2/
%G ru
%F VMUMM_2014_5_a2
E. N. Trusevich. Complexity of certain systems of monomials in calculation by composition circuits. Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 5 (2014), pp. 18-22. http://geodesic.mathdoc.fr/item/VMUMM_2014_5_a2/