|
Журнал вычислительной математики и математической физики, 2012, том 52, номер 10, страницы 1926–1935
(Mi zvmmf9772)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
О сложности задачи дуализации
Е. В. Дюкова, Р. М. Сотнезов 119991 Москва, ул. Вавилова, 40, ВЦ РАН
Аннотация:
Работа посвящена вопросам вычислительной сложности дискретных задач перечисления решений. Введено понятие асимптотически эффективного алгоритма для задачи дуализации, которая сформулирована как задача построения неприводимых покрытий булевой матрицы. Данное понятие предъявляет более слабые требования к числу «лишних» шагов алгоритма по сравнению с понятием асимптотически оптимального алгоритма, введенного впервые ранее. Для случая когда число строк в матрице не меньше числа столбцов (в этом случае не удается построить асимптотически оптимальные алгоритмы для рассматриваемой задачи), показана асимптотическая эффективность алгоритмов, основанных на перечислении с полиномиальной задержкой «совместимых» наборов столбцов булевой матрицы. Аналогичный результат получен для задачи поиска максимальных конъюнкций монотонной булевой функции, заданной конъюнктивной нормальной формой. Библ. 20.
Ключевые слова:
сложность задач перечисления, задача дуализации, максимальная конъюнкция, неприводимое покрытие булевой матрицы, алгоритм с полиномиальной задержкой, асимптотически оптимальный алгоритм поиска неприводимых покрытий, метрические свойства множества покрытий, метрические свойства дизъюнктивных нормальных форм.
Поступила в редакцию: 14.03.2012
Образец цитирования:
Е. В. Дюкова, Р. М. Сотнезов, “О сложности задачи дуализации”, Ж. вычисл. матем. и матем. физ., 52:10 (2012), 1926–1935; Comput. Math. Math. Phys., 52:10 (2012), 1472–1481
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/zvmmf9772 https://www.mathnet.ru/rus/zvmmf/v52/i10/p1926
|
Статистика просмотров: |
Страница аннотации: | 291 | PDF полного текста: | 80 | Список литературы: | 42 | Первая страница: | 18 |
|