Минимальные комплексы граней случайной булевой функции

Для почти всех булевых функций $n$ переменных доказано, что число минимальных относительно меры сложности комплексов граней не превосходит $2^{2^{n-1}\left(1+o\left(1\right)\right)}$, если максимальная длина минимальных и длина кратчайших комплексов граней асимптотически равны. Для аддитивных мер сложности получены эффективно проверяемые достаточные условия, при которых асимптотически равны максимальная длина минимальных и длина кратчайших комплексов граней для почти всех булевых функций. Библиогр. 17.