General upper bound of circuit complexity in an arbitrary infinite complete base (Q1275996)

Let \(A\) be an arbitrary functionally complete system of Boolean functions where each function depends essentially on all its arguments. The complexity function \(L_A(n)\) is introduced by the formula \(L_A(n) = \max_{f}\min_{S} L(S)\), where \(L(S)\) is the complexity of the circuit \(S\) and \(f\) runs over the Boolean functions of \(n\) variables. The note deals with the proof of the following assertion. For an arbitrary infinite basis \(A\) the relation \(L_A(n)\leq C\cdot 2^{n/2}\) is satisfied for all \(n\geq 1\), where \(C\) is an absolute constant (i.e. independent of the basis \(A\)).