RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., 2018, том 25, выпуск 3, страницы 36–94 (Mi da902)

Эта публикация цитируется в 3 статьях

О сложности реализации линейной булевой функции в классе $\pi$-схем

К. Л. Рычков

Институт математики им. С. Л. Соболева СО РАН, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

Аннотация: Для сложности в классе $\pi$-схем линейной булевой функции, существенно зависящей от 6 переменных, на основе метода В. М. Храпченко получена точная нижняя оценка 40. Дано упрощённое доказательство ряда нижних оценок сложности линейных булевых функций, полученных ранее на базе того же метода. Библиогр. 18.

Ключевые слова: булева функция, $\pi$-схема, нижняя оценка сложности.

УДК: 519.714

Статья поступила: 18.09.2017
Переработанный вариант: 10.05.2018

DOI: 10.17377/daio.2018.25.589


 Англоязычная версия: Journal of Applied and Industrial Mathematics, 2018, 12:3, 540–576

Реферативные базы данных:


© МИАН, 2024