RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2018 Volume 25, Issue 3, Pages 36–94 (Mi da902)

This article is cited in 3 papers

Complexity of the realization of a linear Boolean function in the class of $\pi$-schemes

K. L. Rychkov

Sobolev Institute of Mathematics, 4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia

Abstract: Using Khrapchenko's method, we obtain the exact lower bound of 40 for the complexity in the class of $\pi$-schemes of a linear Boolean function depending substantially on 6 variables. We give a simplified proof of several lower bounds for the complexity of linear Boolean functions which are previously obtained on the basis of the same method. Bibliogr. 18.

Keywords: Boolean function, $\pi$-scheme, lower complexity bound.

UDC: 519.714

Received: 18.09.2017
Revised: 10.05.2018

DOI: 10.17377/daio.2018.25.589


 English version:
Journal of Applied and Industrial Mathematics, 2018, 12:3, 540–576

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024