On the Influence of the Depth of Formulas on Their Complexity
Oleg Borisovich Lupanov · Journal of Cybernetics · 1971
Certain classes of control systems wherein the concept of depth is defined in a natural manner (for example, parallel-series contact circuits, valve arrangements) are characterized by the fact that, for almost all functions realizable by them, the asymptotically best schematics can be chosen from a class of schematics of depth bounded by a small constant [1, 2 ]. In this paper it is shown that for individual functions this phenomenon does not in general hold and it is shown that, in the realization of monotonic functions by “positive” formulas on the basis of &, V, the complexity of the functions in a certain specific sequence depends in a very real way on the depth of the formulas.