CSEDays. Theory 2010

Екатеринбург, база отдыха "Аракуль", 19-21 марта

News subscription
Share:

Reviews

Впечатлил уровень докладов и докладчиков, стоит сказать особое спасибо тем, кто их приглашал.
Павел Самолысов / CSEDays. Theory 2010
Home / CSEDays Theory 2010 / Куликов Александр /

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

Author: Куликов Александр

Посмотреть презентацию

Посмотреть видео лекции

Прослушать аудио запись лекции

План лекции

  1. P и NP неформально
  2. Точные алгоритмы
  3. FPT-алгоритмы 
  4. Приближенные алгоритмы 

 
Классы P и NP

Определения

  1. Задача поиска задаётся алгоритмом C, который получает на вход условие I и кандидата на решение S и имеет время работы, ограниченное некоторым полиномом от |I |. S называется решением, если и только если C(S, I ) = true.
  2. NP - класс всех задач поиска. Другими словами, NP класс всех задач, решение для которых может быть быстро проверено.
  3. P - класс задач поиска, решение для которых может быть быстро найдено.
  4. P=NP? Другими словами, существуют ли задачи, решение для которых может быть быстро проверено, но не может быть быстро найдено? Это один из самых важных и самых сложных открытых вопросов Theoretical Computer Science.

Сведения

  1. Говорим, что задача A сводится к задаче B, и пишем A → B, если по эффективному алгоритму для задачи B можно построить эффективный алгоритм для задачи A.
  2. По-другому: если A решить сложно и A → B, то и B решить сложно. То есть B не может быть сильно проще
  3. Задача поиска называется NP-полной, если к ней сводятся все задачи поиска. То есть это универсальный притягивающий объект в классе NP.
  4. Удивительно (на первый взгляд), что такие задачи вообще существуют.

P vs NP

  1. Большинство исследователей считают, что P=NP.
  2. Есть, впрочем, и другие мнения: http://www.win.tue.nl/∼gwoegi/P-versus-NP.htm
  3. В предположении P=NP не существует полиномиальных алгоритмов для NP-трудных задач.

Мотивация

  1. Многим приложениям требуется решать NP-трудные задачи, даже несмотря на то, что решения могут быть найдены только для весьма маленьких размеров входов.
  2. Лучшее понимание NP-трудных задач.
  3. Новые интересные комбинаторные и алгоритмические задачи.
  4. Общая теория.

 
Точные алгоритмы

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

Представим, что у нас есть алгоритм сложности 1.7n для некоторой задачи, который за “разумное” время позволяет решать примеры этой задачи размера не более n0 .

  1. The “hardware” approach: возьмем в 10 раз более быстрый компьютер. Теперь мы можем решать примеры размера n0 + 4.
  2. The “brainware” approach: придумаем алгоритм сложности 1.3n. Это позволит нам решать примеры размера 2*n0.

Другими словами, уменьшение основания экспоненты времени работы алгоритма увеличивает размер решаемых за данное время примеров в константное число раз, в то время как использование более быстрого компьютера способно увеличить размер лишь на константу.

  • 3-клика
  • Анализ алгоритма

Лемма: Алгоритм выдает правильный ответ за время O(nω), где ω ≈ 2.376 - экспонента перемножения матриц (matrix multiplication exponent).

  • Задача о максимальном разрезе

Определение: Задача о максимальном разрезе (maximum cut problem, MAX-CUT) заключается в нахождении такого разбиения вершин графа на две части, при котором количество ребер, концы которых принадлежат разным частям, максимально.

  • Вспомогательный граф
  • Алгоритм Matrix-MAX-CUT(G)

Описание и известные оценки для алгоритма.

 
FTP-алгоритмы

  • Вершинное покрытие и доминирующее множество
  • Сравнение алгоритмов
  • Fixed parameter tractability
  • Задача о пути длины k

Определение: Задачи о пути длины k (k-path problem) заключается в нахождении по данному графу G с двумя выделенными вершинами s и t и числу k простого пути между s и t, содержащего ровно k промежуточных вершин.

  • Color coding 
  • Оценка вероятности ошибки
  • Как же проверять наличие полноцветного пути?

 
Приближенные алгоритмы

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

Алгоритмы, находящие за полиномиальное время для данной оптимизационной задачи решение, которое гарантированно не сильно хуже оптимального.

  • Задача о коммивояжере
  • 2-оптимальный алгоритм

Алгоритм Approx-TSP(G), пример работы и анализ алгоритма.

  • 3/2-оптимальный алгоритм

Алгоритм Approx-TSP-Improved(G), анализ алгоритма, доказательство и известные оценки.