This article is cited in 6 papers

On the complexity of implementation of a system of two monomials by composition circuits

S. A. Korneev

Lomonosov Moscow State University

Abstract: The complexity of implementation of systems of monomials by composition circuits is studied. In such a model, the complexity is understood as the smallest number of composition operations required for computation of a system of monomials. The main result is an exact formula which, for an arbitrary pair of monomials, gives the complexity of their joint implementation by composition circuits.

Keywords: system of monomials, composition circuit, circuit of gates, computational complexity, circuit complexity.

UDC: 519.714.7

Received: 12.12.2019

DOI: 10.4213/dm1604

 English version: Discrete Mathematics and Applications, 2021, 31:2, 113–125

Bibliographic databases:

• 
• 
• 
•