This article is cited in 1 paper

Part 3. Mathematical models

On the behavior of the Shannon function of the implementation complexity of monomials system

S. A. Korneev

Lomonosov Moscow State University

Abstract: In this paper, we examined the computational complexity (minimum possible number of operations) of systems of monomials by circuits using two-input composition operation, which can be considered as a generalization of multiplication operation. We found that growth asymptotic of the Shannon function, characterizing the maximum complexity among systems of $p$ monomials of $q$ variables with exponents no more than $K$, given that $pq \log K \rightarrow \infty$ and some additional restrictions, has the form $ \min(p,q) \log_2 K + \frac{pq}{\log_2(pq)}$.

Keywords: set of monomials, computation complexity, circuit complexity, composition circuit, Shannon function.