Complexity of certain systems of monomials in calculation by composition circuits
E. N. Trusevich · Moscow University Mathematics Bulletin · 2014
The circuit complexity of monomial set computation is studied in the paper. In the model considered here, the complexity means the minimal number of composition operations sufficient for calculating the system from 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 operations only, or multiplication and division operations, or multiplication operations with the ability to use inverse variables. However, this feature of significant “computation strength” is not universal, which is confirmed by an appropriate example. Furthermore, for a system containing two monomials of two variables we obtained an exact complexity value. We have also established that duality reasons do not work (or work poorly) in calculations using composition operation.