О сложности задачи дуализации

Работа посвящена вопросам вычислительной сложности дискретных задач перечисления решений. Введено понятие асимптотически эффективного алгоритма для задачи дуализации, которая сформулирована как задача построения неприводимых покрытий булевой матрицы. Данное понятие предъявляет более слабые требования к числу «лишних» шагов алгоритма по сравнению с понятием асимптотически оптимального алгоритма, введенного впервые ранее. Для случая когда число строк в матрице не меньше числа столбцов (в этом случае не удается построить асимптотически оптимальные алгоритмы для рассматриваемой задачи), показана асимптотическая эффективность алгоритмов, основанных на перечислении с полиномиальной задержкой «совместимых» наборов столбцов булевой матрицы. Аналогичный результат получен для задачи поиска максимальных конъюнкций монотонной булевой функции, заданной конъюнктивной нормальной формой. Библ. 20.