О минимальных комплексах граней в единичном кубе

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