KIAM Main page Web Library  •  Publication Searh  Русский 
Publication

Article collection "Mathematical Problems of Cybernetics" №21, Moscow, 2023
Authors: Lozhkin S.A.
Refined bounds on Shannon's function for complexity of circuits of some classes
Abstract:
Earlier the author proposed rather general approaches and methods for obtaining high accuracy and close to high accuracy asymptotic bounds on Shannon's function for complexity in various classes of circuits. Most of the results obtained with their aid were published in a number of papers, except perhaps for the close to the high accuracy asymptotic bounds on Shannon's function for the complexity of circuits without restrictions on their structure. This paper fills this gap and presents a modified and simplified version of the above-mentioned method -- the synthesis method of circuits in arbitrary basis, that nevertheless allows to obtain the bounds with the required level of accuracy at the account of 'effective' usage of the outputs branching of gates with minimal reduced 'weight'.
Keywords:
Boolean function, circuits of the functional elements, complexity, high accuracy asymptotic bounds
Publication language: russian,  pages: 26 (p. 168-193)
Research direction:
Mathematical problems and theory of numerical methods
Russian source text:
Export link to publication in format:   RIS    BibTeX
About authors:
  • Lozhkin Sergey Andreevich,  orcid.org/0000-0002-8952-6046Lomonosov Moscow State University