• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Новый алгоритм для задачи выполнения наибольшего количества дизъюнктов

ФИО студента: Алфёров Василий Викторович

Руководитель: Близнец Иван Анатольевич

Кампус/факультет: Санкт-Петербургская школа физико-математических и компьютерных наук

Программа: Прикладная математика и информатика (Бакалавриат)

Оценка: 10

Год защиты: 2020

Задача булевой выполнимости – исторически первая задача, для которой была доказана NP-полнота. Её оптимизационная версия, задача максимальной выполнимости, состоящая в выполнении наибольшего количества дизъюнктов в булевой формуле, также является NP-полной. Несмотря на то, что в предположении гипотезы об экспоненциальном времени эти задачи не могут быть решены за субэкспоненциальное время, задача максимальной выполнимости имеет большое количество применений, и подходы к этой задаче активно изучаются. В последние годы исследования версий задачи максимальной выполнимости, параметризованных общим количеством дизъюнктов и количеством выполненных дизъюнктов, сильно продвинулись за счёт введения сильных правил упрощения, основанных на правиле резолюции, и новых техник сведения экземпляра задачи к экземпляру задачи о покрытии множества. Другой важный результат заключается в том, что задача (n, 3)-MAXSAT, параметризованная количеством переменных, решается гораздо быстрее, чем в общем случае. В данной работе рассматривается задача максимальной выполнимости, решаемая относительно длины формулы, то есть суммарного количества литералов во всех дизъюнктах. Несмотря на то, что некоторые новые правила оказываются полезными для такой задачи, большинство из них увеличивают длину формулы и не могут быть применены. В этой работе представлены новые правила упрощения, не увеличивающие длину формулы. Также предлагается новый параметр с пониженной стоимостью 3-переменных, использующий то, что (n, 3)-MAXSAT решается гораздо быстрее, чем общий случай задачи максимальной выполнимо- сти. Комбинация двух методов позволяет получить алгоритм, работающий за время O*(1.093^L). Это улучшает предыдущую верхнюю оценку в O*(1.106^L), полученную Банзалом и Раманом.

Текст работы (работа добавлена 27 мая 2020 г.)

Выпускные квалификационные работы (ВКР) в НИУ ВШЭ выполняют все студенты в соответствии с университетским Положением и Правилами, определенными каждой образовательной программой.

Аннотации всех ВКР в обязательном порядке публикуются в свободном доступе на корпоративном портале НИУ ВШЭ.

Полный текст ВКР размещается в свободном доступе на портале НИУ ВШЭ только при наличии согласия студента – автора (правообладателя) работы либо, в случае выполнения работы коллективом студентов, при наличии согласия всех соавторов (правообладателей) работы. ВКР после размещения на портале НИУ ВШЭ приобретает статус электронной публикации.

ВКР являются объектами авторских прав, на их использование распространяются ограничения, предусмотренные законодательством Российской Федерации об интеллектуальной собственности.

В случае использования ВКР, в том числе путем цитирования, указание имени автора и источника заимствования обязательно.

Реестр дипломов НИУ ВШЭ