Complexity of the Realization of a Linear Boolean Function in the Class of П-Schemes

Complexity of the Realization of a Linear Boolean Function in the Class of П-Schemes Full article

Journal

Journal of Applied and Industrial Mathematics
ISSN: 1990-4789 , E-ISSN: 1990-4797

Output data

Year: 2018, Volume: 12, Number: 3, Pages: 540-576 Pages count : 37 DOI: 10.1134/S1990478918030146

Tags

Boolean function, π-scheme, lower complexity bound

Authors

Rychkov Konstantin Leonidovich ¹

Affiliations

1	Sobolev Institute of Mathematics

Using Khrapchenko’s method, we obtain the exact lower bound of 40 for the complexity in the class of π-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.

Rychkov K.L.
Complexity of the Realization of a Linear Boolean Function in the Class of П-Schemes
Journal of Applied and Industrial Mathematics. 2018. V.12. N3. P.540-576. DOI: 10.1134/S1990478918030146 Scopus OpenAlex

Рычков К.Л.
О сложности реализации линейной булевой функции в классе π-схем
Дискретный анализ и исследование операций. 2018. Т.25. №3. С.36-94. DOI: 10.17377/daio.2018.25.589

Scopus:	2-s2.0-8505212306
OpenAlex:	W2888000245

DB	Citing
OpenAlex	2