Prikladnaya Diskretnaya Matematika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Prikl. Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Prikladnaya Diskretnaya Matematika, 2021, Number 53, Pages 103–119
DOI: https://doi.org/10.17223/20710410/53/7
(Mi pdm749)
 

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
Full-text PDF (709 kB) Citations (3)
References:
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.
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
Citation in format AMSBIB
\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:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Прикладная дискретная математика
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024