Complexity of the Realization of a Linear Boolean Function in the Class of П-Schemes | Sciact - Система учета научной деятельности ИМ СО РАН

Complexity of the Realization of a Linear Boolean Function in the Class of П-Schemes Научная публикация

Журнал

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

Вых. Данные

Год: 2018, Том: 12, Номер: 3, Страницы: 540-576 Страниц : 37 DOI: 10.1134/S1990478918030146

Ключевые слова

Boolean function, π-scheme, lower complexity bound

Авторы

Рычков Константин Леонидович ¹

Организации

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

БД	Цитирований
OpenAlex	2