|
This article is cited in 3 scientific papers (total in 3 papers)
Mathematical Backgrounds of Informatics and Programming
The complexity of implementation of a system of monomials in two variables by composition circuits
S. A. Korneevab a Lomonosov Moscow State University, Moscow, Russia
b Keldysh Institute of Applied Mathematics, Russian Academy of Sciences, Moscow, Russia
Abstract:
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<k}{a^+_{i_l 1}}}, \frac{a^+_{i_k 2}}{\max\limits_{l: l<k}{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.
Keywords:
set of monomials, computation complexity, circuit complexity, composition circuit.
Citation:
S. A. Korneev, “The complexity of implementation of a system of monomials in two variables by composition circuits”, Prikl. Diskr. Mat., 2021, no. 53, 103–119
Linking options:
https://www.mathnet.ru/eng/pdm749 https://www.mathnet.ru/eng/pdm/y2021/i3/p103
|
|