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

Рассматривается задача о соотношении тупиковых и минимальных дизъюнктивных нормальных форм или комплексов граней булевой функции, которая была поставлена С. В. Яблонским в связи с оцениванием сложности алгоритмов минимизации булевых функций. В работе исследуются комплексы граней, минимальные относительно класса мер сложности, для которых сложность комплекса уменьшается при удалении грани и не изменяется при замене некоторых граней на грани изоморфные относительно перестановки координат.
Для отношения числа тупиковых и минимальных комплексов граней функции для любой меры сложности из такого класса получена нижняя оценка логарифма вида $cn2^n$, где $c>1,355\cdot2^{-7}$. При этом логарифм числа тупиковых комплексов может быть порядка $n2^n$ при единственном минимальном комплексе граней, если мера сложности удовлетворяет дополнительному условию: сложность комплекса уменьшается при уменьшении ранга любой грани.
Получены нижние оценки мощности классов функций, по порядку логарифма сравнимые с числом всех функций, для которых отношение числа тупиковых и минимальных комплексов, в том числе при условии единственного минимального комплекса, имеют порядок роста логарифма, равный $n2^n$.