Geodesic
On the complexity of implementation of a~system of three monomials of two variables by composition circuits
Diskretnaya Matematika, Tome 34 (2022) no. 4, pp. 36-51.

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

We study the complexity of implementation of systems of monomials by composition circuits. Here, by the complexity we mean the smallest possible number of operations required for computation of the system of monomials from the variables; under this approach, results of intermediate computations can be used several times. The main result of this paper establishes, for an arbitrary system of three monomials of two variables without zeroth powers, a formula for the complexity of their joint implementation by composition circuits with an additive error which is either 1 or 0.
Keywords: system of monomials, composition circuit, circuit of gates, computational complexity, circuit complexity. 
@article{DM_2022_34_4_a3,
     author = {S. A. Korneev},
     title = {On the complexity of implementation of a~system of three monomials of two variables by composition circuits},
     journal = {Diskretnaya Matematika},
     pages = {36--51},
     publisher = {mathdoc},
     volume = {34},
     number = {4},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2022_34_4_a3/}
}
TY  - JOUR
AU  - S. A. Korneev
TI  - On the complexity of implementation of a~system of three monomials of two variables by composition circuits
JO  - Diskretnaya Matematika
PY  - 2022
SP  - 36
EP  - 51
VL  - 34
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2022_34_4_a3/
LA  - ru
ID  - DM_2022_34_4_a3
ER  - 
%0 Journal Article
%A S. A. Korneev
%T On the complexity of implementation of a~system of three monomials of two variables by composition circuits
%J Diskretnaya Matematika
%D 2022
%P 36-51
%V 34
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2022_34_4_a3/
%G ru
%F DM_2022_34_4_a3
S. A. Korneev. On the complexity of implementation of a~system of three monomials of two variables by composition circuits. Diskretnaya Matematika, Tome 34 (2022) no. 4, pp. 36-51. http://geodesic.mathdoc.fr/item/DM_2022_34_4_a3/

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

[2] Lupanov O. B., Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo Mosk. un-ta, Moskva, 1984, 138 pp.

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

[4] Trusevich E. N., “O slozhnosti vychisleniya nekotorykh sistem odnochlenov skhemami kompozitsii”, Vestn. Mosk. un-ta. Ser. 1. Matem., mekh., 2014, no. 5, 18–22 | MR | Zbl

[5] Korneev S. A., “O slozhnosti realizatsii sistemy iz dvukh monomov skhemami kompozitsii”, Diskretnaya matematika, 32:2 (2020), 15–31

[6] Korneev S. A., “Ob asimptoticheskom povedenii funktsii shennonovskogo tipa, kharakterizuyuschikh slozhnost vychisleniya sistem monomov”, Uch. zapiski Kazanskogo un-ta. Ser. Fiz.-matem. nauki, 162:3 (2021), 300–311

[7] Korneev S. A., “O slozhnosti realizatsii sistemy monomov ot dvukh peremennykh skhemami kompozitsii”, Prikladnaya diskretnaya matematika, 2021, no. 53, 103–119 | Zbl

[8] Korneev S. A., “O povedenii funktsii Shennona slozhnosti realizatsii sistem monomov skhemami kompozitsii”, Intellektualnye sistemy. Teoriya i prilozheniya, 25:3 (2021), 173–188