Abstract:
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 $n<7$).
Fulltext:
PDF file (618 kB)