RUS  ENG
Полная версия
ЖУРНАЛЫ // Прикладная дискретная математика // Архив

ПДМ, 2020, номер 48, страницы 16–21 (Mi pdm701)

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

Теоретические основы прикладной дискретной математики

О взаимно однозначном соответствии между правильными семействами булевых функций и рёберными ориентациями булевых кубов

К. Д. Царегородцев

Московский государственный университет им. М. В. Ломоносова, г. Москва, Россия

Аннотация: Доказывается факт взаимно однозначного соответствия между правильными семействами булевых функций и рёберными ориентациями с единственным стоком на булевых кубах. Данное соответствие позволяет перенести часть результатов, полученных для указанных ориентаций, на язык правильных семейств: получить оценки на число правильных семейств длины $ n \ge 5$ и показать, что задача распознавания правильности семейства является coNP-полной.

Ключевые слова: правильные семейства булевых функций, рёберные ориентации с единственным стоком.

УДК: 519.1+512.5

DOI: 10.17223/20710410/48/2



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


© МИАН, 2024