Author: Куликов Александр
Посмотреть презентацию
Посмотреть видео лекции
Прослушать аудио запись лекции
План лекции
Классы P и NP
Определения
- Задача поиска задаётся алгоритмом C, который получает на вход условие I и кандидата на решение S и имеет время работы, ограниченное некоторым полиномом от |I |. S называется решением, если и только если C(S, I ) = true.
- NP - класс всех задач поиска. Другими словами, NP класс всех задач, решение для которых может быть быстро проверено.
- P - класс задач поиска, решение для которых может быть быстро найдено.
- P=NP? Другими словами, существуют ли задачи, решение для которых может быть быстро проверено, но не может быть быстро найдено? Это один из самых важных и самых сложных открытых вопросов Theoretical Computer Science.
Сведения
- Говорим, что задача A сводится к задаче B, и пишем A → B, если по эффективному алгоритму для задачи B можно построить эффективный алгоритм для задачи A.
- По-другому: если A решить сложно и A → B, то и B решить сложно. То есть B не может быть сильно проще
- Задача поиска называется NP-полной, если к ней сводятся все задачи поиска. То есть это универсальный притягивающий объект в классе NP.
- Удивительно (на первый взгляд), что такие задачи вообще существуют.
P vs NP
- Большинство исследователей считают, что P=NP.
- Есть, впрочем, и другие мнения: http://www.win.tue.nl/∼gwoegi/P-versus-NP.htm
- В предположении P=NP не существует полиномиальных алгоритмов для NP-трудных задач.
Мотивация
- Многим приложениям требуется решать NP-трудные задачи, даже несмотря на то, что решения могут быть найдены только для весьма маленьких размеров входов.
- Лучшее понимание NP-трудных задач.
- Новые интересные комбинаторные и алгоритмические задачи.
- Общая теория.
Точные алгоритмы
- Точные алгоритмы для NP-трудных задач
- Мотивация
Представим, что у нас есть алгоритм сложности 1.7n для некоторой задачи, который за “разумное” время позволяет решать примеры этой задачи размера не более n0 .
- The “hardware” approach: возьмем в 10 раз более быстрый компьютер. Теперь мы можем решать примеры размера n0 + 4.
- 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), анализ алгоритма, доказательство и известные оценки.