The complexity of implementation of a system of~monomials in two variables by composition circuits

S. A. Korneev

Prikladnaâ diskretnaâ matematika, no. 3 (2021), pp. 103-119

Résumé

The computational complexity of systems of monomials by compositional circuits is investigated. In such a model, complexity is understood as the smallest number of composition operations required to compute a system of monomials. For this model we have found the computational complexity of a system of $p$ monomials in two variables up to a term that grows as $p$. By $l_{sh}(A)$ we mean the complexity of implementation of the system of monomials defined by the matrix $A$ by composition circuits. For any integer $a$ we assume $a^+=\max{(a,1)}$. Theorem. Let $A=(a_{ij})$ be a $(p \times q)$-matrix without zero rows and columns consisting of non-negative integers. Then $G(A) \le l_{sh}(A) \le G(A)+2p-3$, where \begin{equation*} G(A)=\max\limits_{(i_1, \ldots, i_p) \in S_p}{{\textstyle\sum\limits_{k=1}^{p}}{\left\lceil\log{\max{\left(\frac{a^+_{i_k 1}}{\max\limits_{l: l}{a^+_{i_l 1}}}, \frac{a^+_{i_k 2}}{\max\limits_{l: l}{a^+_{i_l 2}}}, 1\right)}}\right\rceil}}. \end{equation*} We also show that for composition circuits, in contrast to other models, the asymtotical growth of the computational complexity of system of monomials in two variables in the general case is not determined by any improper subset of this system of monomials.

Détail

Keywords: set of monomials, computation complexity, circuit complexity
Mots-clés : composition circuit.