Аннотация:
Доказано, что при n=3,5 и при n, равном степени
двойки, любое минимальное правильное разбиение множества рёбер
n-мерного куба является совершенным. Следствием этих результатов
является описание классов всех минимальных
параллельно-последовательных контактных схем (π-схем),
реализующих линейные булевы функции, существенно зависящие от n
переменных при соответствующих значениях n. Библиогр. 16.
Ключевые слова:
булева функция, π-схема, правильное разбиение множества рёбер n-мерного куба, нижняя оценка сложности.
Исследование выполнено при финансовой поддержке Программы фундаментальных научных
исследований СО РАН № I.5.1 (проект № 0314–2019–0016).
Статья поступила: 10.06.2019 Переработанный вариант: 29.07.2019 Принята к публикации: 28.08.2019
Тип публикации:
Статья
УДК:519.714
Образец цитирования:
К. Л. Рычков, “О совершенности минимальных правильных разбиений множества рёбер n-мерного куба”, Дискретн. анализ и исслед. опер., 26:4 (2019), 74–107