The asymptotically best method for synthesizing limited-depth Boolean recursive schemes (Q1706039): Difference between revisions

The author considers a general recursive scheme of functional elements (in short, RSFE), with limited depth \(r\), and constructed from multi-output functional elements. Among other things, the author derives a lower estimate of the Shannon function for the complexity of schemes of this class and obtains upper estimates for the complexity of some specific functions and systems of functions in this class of schemes. The above estimations allow the author to determine the asymptotics of the Shannon function \(L^r(n)\) for their complexity, namely, \(L^r(n)\sim r\frac{2^{\frac{n}{r}}}{\root r \of{n}}\). It can be noticed that the best way of synthesizing the RSFE asymptotically is based on Lupanov's asymptotically best method whose description is taken from [\textit{S. V. Yablonskiĭ}, Elements of mathematical cybernetics (Russian). Moscow: Vyssh. Shkola (2007)].