Geodesic
Complexity of certain systems of monomials in calculation by composition circuits
Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 5 (2014), pp. 18-22 
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/
@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},
     year = {2014},
     number = {5},
     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
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
%U http://geodesic.mathdoc.fr/item/VMUMM_2014_5_a2/
%G ru
%F VMUMM_2014_5_a2

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.

[1] Shirshov A.I., “Nekotorye algoritmicheskie problemy dlya algebr Li”, Sib. matem. zhurn., 3 (1962), 292–296 | Zbl

[2] Lupanov O.B., “O sinteze nekotorykh klassov upravlyayuschikh sistem”, Problemy kibernetiki, 10, Fizmatlit, M., 1963, 63–97

[3] Merekin Yu.V., “O porozhdenii slov s ispolzovaniem operatsii kompozitsii”, Diskretn. analiz i issled. operatsii. Ser. 1, 10:4 (2003), 70–78 | MR | Zbl

[4] Trusevich E.N., “O slozhnosti realizatsii skhemami kompozitsii sistem iz dvukh monomov ot dvukh peremennykh”, Mat-ly VIII molodezhnoi nauchnoi shkoly po diskretn. matem. i ee pril. (Moskva, 24–29 oktyabrya 2011 g.), v. 2, M., 2011, 40–44

[5] Kochergin V.V., “O slozhnosti vychisleniya pary odnochlenov ot dvukh peremennykh”, Diskretn. matem., 17:4 (2005), 116–142 | DOI | Zbl

[6] Kochergin V.V., “Ob asimptotike slozhnosti additivnykh vychislenii sistem tselochislennykh lineinykh form”, Diskretn. analiz i issled. operatsii. Ser. 1, 13:2 (2006), 38–58 | Zbl

[7] Kochergin V.V., “O slozhnosti sovmestnogo vychisleniya trekh elementov svobodnoi abelevoi gruppy s dvumya obrazuyuschimi”, Diskretn. analiz i issled. operatsii. Ser. 1, 15:2 (2008), 23–64 | MR | Zbl

[8] Trusevich E.N., “Ob osobennostyakh odnoi mery slozhnosti tselochislennykh matrits”, Mat-ly XI Mezhdunar. seminara “Diskretnaya matematika i ee prilozheniya”, posv. 80-letiyu so dnya rozhdeniya O. B. Lupanova (Moskva, 18–23 iyunya 2012 g.), M., 2012, 171–173

[9] Kochergin V.V., “Ob odnom sootnoshenii dvukh mer slozhnosti vychisleniya sistem odnochlenov”, Vestn. Mosk. un-ta. Matem. Mekhan., 2009, no. 4, 8–13 | MR | Zbl

[10] Sidorenko A.F., “Slozhnost additivnykh vychislenii semeistv tselochislennykh lineinykh form”, Zap. nauch. seminarov LOMI, 105, 1981, 53–61 | Zbl