Материалов:
678 583

Репозиториев:
29

Авторов:
475 470

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

Дата публикации: 2020

Дата публикации в реестре: 2020-07-05T11:55:43Z

Аннотация:

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

Тип: статьи в журналах

Источник: Прикладная дискретная математика. 2020. № 48. С. 16-21


Связанные документы (рекомендация CORE)