Upper bounds for the formula size of symmetric Boolean functions
Igor' Sergeevich Sergeev · Russian Mathematics · 2014
We prove that the complexity of the implementation of the counting function of n Boolean variables by binary formulas is at most n 3.03, and it is at most n 4.47 for DeMorgan formulas. Hence, the same bounds are valid for the formula size of any threshold symmetric function of n variables, particularly, for the majority function. The following bounds are proved for the formula size of any symmetric Boolean function of n variables: n 3.04 for binary formulas and n 4.48 for DeMorgan ones. The proof is based on the modular arithmetic.