Задача монотонной дуализации и ее обобщения: асимптотические оценки числа решений

Исследуются вопросы построения эффективных алгоритмов для труднорешаемых дискретных задач. Рассматриваются перечислительные задачи, труднорешаемость которых имеет два аспекта: экспоненциальный рост числа решений при увеличении размера задачи и сложность их нахождения (перечисления). Главной перечислительной задачей считается дуализация монотонной конъюнктивной нормальной формы. Эквивалентной задачей является поиск неприводимых покрытий булевой матрицы. Для задачи поиска неприводимых покрытий булевой матрицы и обобщений этой задачи на случай целочисленной матрицы получены асимптотики типичного числа решений. Эти оценки необходимы, в частности, для обоснования существования асимптотически оптимальных алгоритмов монотонной дуализации и ее обобщений. Библ. 15.