Abstract:
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.
Key words:set of monomials, composition circuit, circuit of functional elements, circuit complexity.
Fulltext:
PDF file (344 kB)