Matematičeskie zametki, Tome 9 (1971) no. 1, pp. 35-40
Citer cet article
V. M. Khrapchenko. Complexity of the realization of a linear function in the class of $\Pi$-circuits. Matematičeskie zametki, Tome 9 (1971) no. 1, pp. 35-40. http://geodesic.mathdoc.fr/item/MZM_1971_9_1_a4/
@article{MZM_1971_9_1_a4,
author = {V. M. Khrapchenko},
title = {Complexity of the realization of a linear function in the class of $\Pi$-circuits},
journal = {Matemati\v{c}eskie zametki},
pages = {35--40},
year = {1971},
volume = {9},
number = {1},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/MZM_1971_9_1_a4/}
}
TY - JOUR
AU - V. M. Khrapchenko
TI - Complexity of the realization of a linear function in the class of $\Pi$-circuits
JO - Matematičeskie zametki
PY - 1971
SP - 35
EP - 40
VL - 9
IS - 1
UR - http://geodesic.mathdoc.fr/item/MZM_1971_9_1_a4/
LA - ru
ID - MZM_1971_9_1_a4
ER -
%0 Journal Article
%A V. M. Khrapchenko
%T Complexity of the realization of a linear function in the class of $\Pi$-circuits
%J Matematičeskie zametki
%D 1971
%P 35-40
%V 9
%N 1
%U http://geodesic.mathdoc.fr/item/MZM_1971_9_1_a4/
%G ru
%F MZM_1971_9_1_a4
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$.
