RUS  ENG
Full version
JOURNALS // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika // Archive

Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2022 Number 3, Pages 32–40 (Mi vmumm4473)

This article is cited in 1 paper

Mathematics

Refined bounds on Shannon’s function for complexity of circuits of functional elements

S. A. Lozhkin

Lomonosov Moscow State University, Faculty of Computational Mathematics and Cybernetics

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 one of the above-mentioned methods, which, nevertheless, allows one to obtain bounds with the required accuracy.

Key words: Boolean function, circuits of the functional elements, complexity, high accuracy asymptotic bounds.

UDC: 519.95

Received: 10.02.2022


 English version:
Moscow University Mathematics Bulletin, Moscow University Måchanics Bulletin, 2022, 77:3, 144–153

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025