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 lsh(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=(aij) be a (p×q)-matrix without zero rows and columns consisting of non-negative integers. Then G(A)⩽, 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.
Bibliographic databases:
Document Type:
Article
UDC:519.714
Language: Russian
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
\Bibitem{Kor21}
\by S.~A.~Korneev
\paper The complexity of implementation of a system of~monomials in two variables by composition circuits
\jour Prikl. Diskr. Mat.
\yr 2021
\issue 53
\pages 103--119
\mathnet{http://mi.mathnet.ru/pdm749}
\crossref{https://doi.org/10.17223/20710410/53/7}
Linking options:
https://www.mathnet.ru/eng/pdm749
https://www.mathnet.ru/eng/pdm/y2021/i3/p103
This publication is cited in the following 3 articles:
S. A. Korneev, “On the complexity of implementation of a system of three monomials of two variables by composition circuits”, Discrete Math. Appl., 34:2 (2024), 89–101
Vadim Vasil'evich Kochergin, “Bellman's, Knut's, Lupanov's, Pippenger's problems and their variations as generalizations of the addition chain problem”, MVK, 2022, no. 20, 119
S. A. Korneev, “O povedenii funktsii Shennona slozhnosti realizatsii sistem monomov skhemami kompozitsii”, Intellektualnye sistemy. Teoriya i prilozheniya, 25:3 (2021), 173–188