EN|RU

Том 19, номер 3, 2012 г., Стр. 79-99

УДК 519.95
Чухров И. П. 
О минимальных комплексах граней в единичном кубе

Аннотация:
Рассматривается задача построения минимальных комплексов граней в единичном $n$-мерном кубе относительно класса мер сложности, для которых сложность комплекса не изменяется при замене некоторых граней гранями, изоморфными относительно перестановки координат. Этот класс содержит все известные меры сложности, используемые при минимизации булевых функций в классе дизъюнктивных нормальных форм (д.н.ф.). Показано, что число комплексов из граней размерности не более $k$, которые являются минимальными для всех мер сложности из этого класса, совпадает по порядку логарифма с числом комплексов из не более $2^{n-1}$ различных граней размерности не более $k$ при $1\le k\le c\cdot n$ и $c<0.5$. Число функций с “большим” числом минимальных комплексов совпадает по порядку логарифма с числом всех функций. Аналогичные оценки справедливы для максимального числа д.н.ф. булевой функции, которые являются минимальными для всех мер сложности из указанного класса. Полученные результаты показывают, что проблемы трудоёмкости при минимизации булевых функций определяются структурными свойствами множества вершин булевой функции в единичном кубе, т.е. свойствами области, на которой минимизируется функционал, а не свойствами функционала меры сложности.
Ил. 1, библиогр. 9.

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

Чухров Игорь Петрович 1
1. Институт автоматизации проектирования РАН,
ул. 2-я Брестская, 19/18, 123056 Москва, Россия
е-mail: chip@icad.org.ru

Статья поступила 18 июня 2011 г.

 © Институт математики им. С. Л. Соболева, 2015