Алгоритмы для 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.7ⁿ для некоторой задачи, который за “разумное” время позволяет решать примеры этой задачи размера не более n₀ .

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

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

• 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), анализ алгоритма, доказательство и известные оценки.