Часть 2. Специальные вопросы теории интеллектуальных систем

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

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

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

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

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