RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2014 Volume 11, Pages 165–184 (Mi semr478)

This article is cited in 3 papers

Discrete mathematics and mathematical cybernetics

Lower bounds on the formula complexity of a linear Boolean function

K. L. Rychkov

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk

Abstract: Given proof of the lower boundaries of the computational complexity of the linear Boolean function $x_1+\ldots+x_n=1 \pmod 2$ by formulas in the basis $\{\vee,\wedge,^-\}$. It is proved that for $n=6$ this complexity is not less than 40. Earlier, this result was obtained Cherukhin with use of computer calculations [1]. Given a simplified proof of the lower bound, published at [2]: for even $n\neq2^k$ the complexity is not less than $n^2+2$, for odd $n\geq5$ the complexity is not less than $n^2+3$.

Keywords: lower bounds on the formula complexity, formulas, $\pi$-schemes.

UDC: 519.714

MSC: 03D15

Received January 30, 2014, published March 2, 2014



© Steklov Math. Inst. of RAS, 2025