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

Дискретн. анализ и исслед. опер., 2019, том 26, выпуск 4, страницы 74–107 (Mi da938)

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

О совершенности минимальных правильных разбиений множества рёбер $n$-мерного куба

К. Л. Рычков

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

Аннотация: Доказано, что при $n=3, 5$ и при $n,$ равном степени двойки, любое минимальное правильное разбиение множества рёбер $n$-мерного куба является совершенным. Следствием этих результатов является описание классов всех минимальных параллельно-последовательных контактных схем ($\pi$-схем), реализующих линейные булевы функции, существенно зависящие от $n$ переменных при соответствующих значениях $n$. Библиогр. 16.

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

УДК: 519.714

Статья поступила: 10.06.2019
Переработанный вариант: 29.07.2019
Принята к публикации: 28.08.2019

DOI: 10.33048/daio.2019.26.662



© МИАН, 2024