Алгоритмы для NP-трудных задач

Алгоритмы для NP-трудных задач

Многие возникающие на практике задачи (например, составление расписаний, доставка грузов, верификация аппаратного и программного обеспечения) являются NP-трудными. Это, в частности, означает, что мы до сих пор не знаем алгоритмов, которые решали бы эти задачи за приемлемое в худшем случае время. С теоретической точки зрения исследования, посвящённые изучению алгоритмов для NP-трудных задач, можно разделить на три следующих направления.

Точные алгоритмы для NP-трудных задач 

Основной целью данного направления является построение всё более быстрых алгоритмов для NP-трудных задач и получение нижних оценок на время работы таких алгоритмов в предположении популярных теоретико-сложностных гипотез. Что более удивительно и с первого взгляда кажется невозможным, новые быстрые алгоритмы иногда позволяют доказать нижние оценки, что связывает эту область с важнейшими проблемами теории сложности. Каждую NP-трудную задачу можно решить полным перебором всех кандидатов на решение. Всегда ли можно избежать такого полного перебора? Даже ответа на этот вопрос мы до сих пор не знаем. Самым ярким примером является задача выполнимости, для которой до сих пор неизвестно алгоритма, работающего быстрее, чем за время 2^n (где n — число переменных входной формулы). При этом для этой задачи есть эвристические алгоритмы, хорошо работающие на практике. Однако для многих задач такие алгоритмы всё же известны: например, для задачи раскраски, для задачи о максимальном разрезе, для задачи 3-выполнимости, для задачи о кратчайшей общей надстроке. Многие такие алгоритмы используют неожиданные красивые идеи из разных областей алгоритмов и математики.

Параметризованные алгоритмы для NP-трудных задач

Тот факт, что задача является NP-трудной, означает лишь, что мы не знаем алгоритма, эффективно решающего её во всех случаях. Но вполне может оказаться, что есть эффективные алгоритмы для её частных случаев. Например, многие NP-трудные задачи на графах эффективно решаются методом динамического программирования в случае, когда входной граф является деревом. Решаются они эффективно и в случае, когда входной граф достаточно “похож” на дерево. Параметризованной сложностью называется сложность вычислительной задачи как функции от некоторого параметра входных данных. Есть много интересных параметров для рассмотрения: например, размер ответа, степень похожести графа на дерево. Параметризованная сложность также изучает вопрос эффективного сжимания задачи, в частности, вопрос о эффективном преобразовании входа задачи в эквивалентный новый, размер которого будет зависеть только от значения параметра. Например, вопрос о существовании вершинного покрытия размера k в произвольном графе можно за полиномиальное время свести к вопросу существования такого вершинного покрытия в графе размера f(k) (этот размер не зависит от размера исходного графа!). В области параметризованных алгоритмов изучаются как такие сжимающие сведения, так и доказательства того, что слишком хороших таких сжатий не существует. Для ответа на такие вопросы зачастую требуются нетривиальные красивые комбинаторные, сложностные и алгоритмические идеи. 

Приближённые алгоритмы для NP-трудных задач

Часто интересны даже решения, не являющиеся оптимальными, а отличающиеся от оптимального в некоторое контролируемое число раз, если такие решения можно найти быстро. Для некоторых задач даже таких алгоритмов не может быть, если P не равно NP. К примеру, мы не можем приблизить значение минимального пути коммивояжера в полном взвешенном графе ни с какой разумной точностью. В некоторых задачах такие приближения удается получить. Например, для задачи о минимальном вершинном покрытии известен простой алгоритм, выдающий ответ, отличающийся от оптимального не более чем в два раза. Если для задачи вершинного покрытия оказывается, что такой алгоритм оказывается почти оптимальным (разумеется, в некоторых предположениях), для многих задач зазор между верхней границей и нижней остается внушительным и дает огромный простор для исследований. В доказательствах верхних и нижних оценок возникают удивительно красивые вещи как из комбинаторики, так и из непрерывных задач оптимизации, к примеру, многие приближенные алгоритмы основаны на решении ослабленных задач, которые мы можем записать с помощью линейного программирования, и вопрос построения “комбинаторных” алгоритмов остается открытым. 

 

Сотрудники кафедры:  И.А.Близнец Э.А.Гирш, Н.А.Карпов, А.С.Куликов, А.В.Смаль

 

Публикации сотрудников кафедры

  1. E. Dantsin, A. Goerdt, E. A. Hirsch, R. Kannan, J. Kleinberg, C. Papadimitriou, P. Raghavan, U. Schöning. A Deterministic (2-2/(k+1))^n Algorithm for k-SAT Based on Local Search. Theoretical Computer Science 289/1, 2002, pp. 69-83.
  2. E. Dantsin, E. A. Hirsch, A. Wolpert. Algorithms for SAT Based on Search in Hamming Balls. STACS 2004: 141-151.
  3. J. Gramm, E. A. Hirsch, R. Niedermeier, P. Rossmanith, New Worst-Case Upper Bounds for MAX-2-SAT with Application to MAX-CUT. Discrete Applied Mathematics 130/2: 139-155, 2003.
  4. E. A. Hirsch. New Worst-Case Upper Bounds for SAT. Journal of Automated Reasoning 24(4): 397-420, 2000.
  5. E. A. Hirsch. Local Search Algorithms for SAT: Worst-Case Study. Journal of Automated Reasoning 24(1/2): 127-143, 2000.
  6. E. A. Hirsch. Worst-case study of local search for MAX-k-SAT. Discrete Applied Mathematics 130/2: 173-184, 2003.
  7. E. A. Hirsch, A. Kojevnikov. UnitWalk: A new SAT solver that uses local search guided by unit clause elimination. Annals of Mathematics and Artificial Intelligence 43(1-4):91-111, 2005.
  8. Arist Kojevnikov, Alexander S. Kulikov. A new approach to proving upper bounds for MAX-2-SAT. SODA 2006: 11-17
  9. Alexander S. Kulikov, Konstantin Kutzkov. New Bounds for MAX-SAT by Clause Learning. CSR 2007: 194-204
  10. Ivan Bliznets, Alexander Golovnev. A New Algorithm for Parameterized MAX-SAT. IPEC 2012: 37-48
  11. Ivan Bliznets, Fedor V. Fomin, Michal Pilipczuk, Yngve Villanger. Largest Chordal and Interval Subgraphs Faster Than 2^n. ESA 2013: 193-204
  12. Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin. Solving 3-Superstring in 3^{n/3} Time. MFCS 2013: 480-491
  13. Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin. Approximating Shortest Superstring Problem Using de Bruijn Graphs. CPM 2013: 120-129
  14. Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, Michal Pilipczuk. A Subexponential Parameterized Algorithm for Proper Interval Completion. ESA 2014: 173-184
  15. Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin. Families with Infants: A General Approach to Solve Hard Partition Problems. ICALP (1) 2014:551-562
  16. Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin. Lower Bounds for the Graph Homomorphism Problem. ICALP (1) 2015: 481-493
  17. Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov. Parameterized Complexity of Secluded Connectivity Problems. FSTTCS 2015: 408-419
  18. Alexander S. Kulikov, Sergey Savinov, Evgeniy Sluzhaev. Greedy Conjecture for Strings of Length 4. CPM 2015: 307-315
  19. Ivan Bliznets, Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov, Saket Saurabh. Parameterized Complexity of Superstring Problems. CPM 2015: 89-99
  20. Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala. Tight Bounds for Graph Homomorphism and Subgraph Isomorphism. SODA 2016: 1643-1649
  21. Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukás Mach, Michal Pilipczuk. Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems. SODA 2016: 1132-1151
  22. Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, Michal Pilipczuk. Subexponential parameterized algorithm for Interval Completion. SODA 2016: 1116-1131
  23. Ivan Bliznets, Marek Cygan, Pawel Komosa, Michal Pilipczuk. Hardness of Approximation for H-Free Edge Modification Problems. APPROX-RANDOM 2016:3:1-3:17

 

Квалификационные работы

  1. А. С. Куликов. Построение алгоритмов для задач булевой логики при помощи автоматизации, комбинированных мер сложности и запоминания дизъюнктов. Диссертация на соискание степени к.ф.-м.н. ПОМИ РАН, 2009.
  2. А. Г. Головнёв. Приближенные алгоритмы решения перестановочных задач. Магистерская диссертация. СПбАУ РАН, 2012.
  3. С. В. Савинов. Верхняя оценка для задачи выполнимости булевых схем.  Магистерская диссертация. СПбАУ РАН, 2014.
  4. И. А. Михайлин. Алгоритмы для NP-трудных задач, основанные на быстром преобразовании Фурье. Магистерская диссертация. СПбАУ РАН, 2014.
  5. Н. А. Карпов. Параметризованные алгоритмы для задач кластеризации. Магистерская диссертация. СПбАУ РАН, 2016.
  6. И. А. Близнец. Новые верхние оценки для задач максимальной выполнимости. Магистерская диссертация. СПбАУ РАН, 2012.
  7. И. А. Близнец. Алгоритмы и нижние оценки на вычислительную сложность задач модификации графов. Диссертация на соискание степени кандидата физико-математических наук. ПОМИ РАН, 2016.