Upper estimate of realization complexity of linear functions in a basis consisting of multi-input elements

Yu. A. Kombarov

Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 5 (2015), pp. 47-50

Résumé

The paper is devoted to realization of parity functions by circuits in the basis $U_\infty$. This basis contains all functions of form $(x_1^{\sigma_1}\\ldots\ x_k^{\sigma_k})^{\beta}$. We present method of constructing circuts for pairity function of $n$ variables with complexity of $\lfloor (7n-4)/3\rfloor$. This improves previous known upper bound of $U_\infty$-complexity of parity function, that was $\lceil (5n-1)/2\rceil$. It is also shown that constructed circuits are minimal for very small $n$ (for $n7$).