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/