Compositional complexity of Boolean functions

We define two measures, γ and c, of complexity for Boolean functions. These measures are related to issues of functional decomposition which (for continuous functions) were studied by Arnol'd, Kolmogorov, Vitu?kin and others in connection with Hilbert's 13th Problem. This perspective was first applied to Boolean functions in [1]. Our complexity measures differ from those which were considered earlier [3, 5, 6, 9, 10] and which were used by Ehrenfeucht and others to demonstrate the great complexity of most decision procedures. In contrast to other measures, both γ and c (which range between 0 and 1) have a more combinatorial flavor and it is easy to show that both of them are close to 0 for literally all “meaningful” Boolean functions of many variables. It is not trivial to prove that there exist functions for which c is close to 1, and for γ the same question is still open. The same problem for all traditional measures of complexity is easily resolved by statistical considerations.