|
Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports], 2014, Volume 11, Pages 165–184
(Mi semr478)
|
|
|
|
This article is cited in 3 scientific papers (total in 4 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.
Received January 30, 2014, published March 2, 2014
Citation:
K. L. Rychkov, “Lower bounds on the formula complexity of a linear Boolean function”, Sib. Èlektron. Mat. Izv., 11 (2014), 165–184
Linking options:
https://www.mathnet.ru/eng/semr478 https://www.mathnet.ru/eng/semr/v11/p165
|
Statistics & downloads: |
Abstract page: | 173 | Full-text PDF : | 53 | References: | 41 |
|