RUS  ENG
Full version
JOURNALS // Matematicheskie Zametki // Archive

Mat. Zametki, 1971 Volume 9, Issue 1, Pages 35–40 (Mi mzm9639)

This article is cited in 46 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:


© Steklov Math. Inst. of RAS, 2024