This article is cited in 48 papers

Complexity of the realization of a linear function in the class of $\Pi$-circuits

V. M. Khrapchenko

Applied Mathematics Institute, Academy of Sciences of the USSR

Abstract: It is proved that the linear function $g_n(x_1,\dots,x_n)=x_1+\dots+x_n\mod2$ is realized in the class of $\Pi$-circuits with complexity $L_\pi(g_n)\geqslant n^2$. Combination of this result with S. V. Yablonskii's upper bound yields $L_\pi(g_n)\genfrac{}{}{0pt}{}{\smile}{\frown} n^2$.

UDC: 51.01.16

Received: 23.04.1970

 English version: Mathematical Notes, 1971, 9:1, 21–23

Bibliographic databases:

• 
•