On the synthesis and complexity of formulae with bounded depth of alternation (Q1759151)

In this paper networks and formulae in a standard basis of the functional elements \textit{and}, \textit{or} and \textit{negation} with a weight of 1 that implement Boolean functions are considered. The alternation depth of the formula considered as a particular case of a circuit of functional elements is equal to \(a\) if the maximum number of variations of the gates' types on sequences, each being a path and not containing negations connected to the inputs, is \(a-1\). For any \(a\) (\(a\geq 2\)), the complexity \(L^{(a)}(f)\) of the function \(f\) is the minimum complexity of the formulae that compute it and whose alternation depth is not greater than \(a\) and the Shannon complexity \(L^{(a)}(n)\) is the maximum complexity \(L^{a}(f)\), where the maximum is taken over all functions \(f\) of \(n\) Boolean variables. Lupanov proved that \(L^{(a)}(n)\) is asymptotically equal to \(2^{n}/\log n\) for any \(a\geq 3\). The main result of this paper is that, for any natural number \(a\) (\(a\geq 3\)), the following asymptotic estimation is true: \(L^{(a)}(n)=\frac{2^{n}}{\log n}(1+(\log ^{[a-1]}n \pm O(1))/\log n)\), where all logarithms are binary and \(\log ^{[a]}n\) is the \(a\) times iterated logarithm of \(n\).