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

Исследуются булевы функции, которые сочетают экстремальные значения характеристик сложности минимизации, неприменимость локальных методов сокращения трудоёмкости перебора и невозможность эффективного использования достаточных условий минимальности. Построены квазициклические функции, которые обладают свойствами циклических и поясковых функций, доминирования множеств вершин, выполнимостью достаточных условий минимальности, основанных на независимых семействах множеств. Для таких функций получены экспоненциальные нижние оценки протяжённости и специальных множеств, а также дважды экспоненциальная нижняя оценка числа кратчайших и минимальных комплексов граней с различными множествами собственных вершин. Библиогр. 13.