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

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



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






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


Diskr. Mat., 2020, Volume 32, Issue 2, Pages 15–31 (Mi dm1604)  

On the complexity of system of two monomials realization by composition circuits

S. A. Korneev

Lomonosov Moscow State University

Abstract: In this paper we study the curcuit complexity of monomials systems computation. In the considered computational model complexity means the minimal number of composition operations sufficient to compute the system of monomials. The main result of given paper — the exact formula for curcuit compexity of two-monomial system computation is established.

Keywords: set of monomials, composition curcuit, circuit of functional elements, computational complexity, curcuit complexity.

Funding Agency Grant Number
Russian Foundation for Basic Research 18-01-00337-а


DOI: https://doi.org/10.4213/dm1604

Full text: PDF file (494 kB)
First page: PDF file
References: PDF file   HTML file

UDC: 519.714.7
Received: 12.12.2019

Citation: S. A. Korneev, “On the complexity of system of two monomials realization by composition circuits”, Diskr. Mat., 32:2 (2020), 15–31

Citation in format AMSBIB
\Bibitem{Kor20}
\by S.~A.~Korneev
\paper On the complexity of system of two monomials realization by composition circuits
\jour Diskr. Mat.
\yr 2020
\vol 32
\issue 2
\pages 15--31
\mathnet{http://mi.mathnet.ru/dm1604}
\crossref{https://doi.org/10.4213/dm1604}


Linking options:
  • http://mi.mathnet.ru/eng/dm1604
  • https://doi.org/10.4213/dm1604
  • http://mi.mathnet.ru/eng/dm/v32/i2/p15

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Дискретная математика
    Number of views:
    This page:39
    References:2
    First page:2

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020