Вычислительная сложность Классы сложности P и NP. Сергей Казаков, аспирант каф. КТ, НИУ ИТМО
Как все начиналось… Начало 1960-х годов Alan Cobham, 1964 Jack Edmonds, 1965 Они ввели сложностные классы 2
Разрешимые и неразрешимые задачи Проблема останова – неразрешимая задача Доказательство – от противного. 3
Сложностный класс P Класс P класс задач, разрешимых на детерминированной машине Тьюринга за полиномиальное время 4
Класс P. Примеры-1 Посчитать сумму чисел Посчитать произведение чисел Проверка простоты числа Сортировка массива Определение связности графа Эйлеров путь/цикл 5
Эйлеров путь/цикл in P Путь, проходящий по всем ребрам графа, и при этом только по одному разу Граф Кёнигсбергских мостов: Эйлер (1735 год): цикл существует граф связный и все вершины четной степени 6
Эйлеров путь 7
Эйлеров цикл procedure find_all_cycles (v): 1. пока есть цикл, проходящий через v 1. находим его 2. добавляем все вершины цикла к ответу 3. удаляем цикл из графа 2. идем по вершинам из ответа и для каждой рекурсивно вызываем себя find_all_cycles(nv) Working Time – O(M), M – число ребер 8
Сложностный класс NP Класс NP класс задач, у которых есть сертификат решения, который можно быстро (за полином) проверить на машине Тьюринга. Класс NP класс задач, которые можно быстро решить (за полином) на недетерминированной машине Тьюринга. 9
Класс NP. Примеры-1 Задача выполнимости булевых форму (SAT) Определение наличия в графе гамильтонова цикла Задача о коммивояжёре Задача поиска вершинного покрытия графа 10
Гамильтонов путь/цикл Гамильтонов путь путь в графе, содержащий каждую вершину графа ровно один раз Гамильтонов цикл – гамильтонов путь, начальная и конечная вершина которого совпадают 11
Гамильтонов путь/цикл 12
Задача коммивояжёра Задача коммивояжёра (англ. Travelling salesman problem, TSP) 13
NP-трудные и NP-полные задачи Сведение по Карпу: P1 сводится к P2 f: (p P1 f(p) P2) NP-трудность: P1 – NP-трудная задача, если P2 NP, P2 сводится к P1 NP-полная задача: из NP и NP-трудная 14
Соотношения P и NP 15
NP-трудные и NP-полные задачи Стивен Кук (1971 год): термин «NP-полная задача» задача SAT была первой задачей, для которой доказывалось это свойство. Определение наличия в графе гамильтонова цикла – NP-полная Задача о коммивояжёре – с оптимизацией – NP-трудная не длиннее k – NP-полная 16
Приближенные решения Многие задачи, представляющие практический интерес – NP-полные Для них маловероятно найти точный алгоритм с полиномиальным временем работы При небольшом объеме входных данных может подойти алгоритм, время работы которого выражается показательной функцией Иногда удается выделить важные частные случаи, разрешимые в течение полиномиального времени 17
Приближенные решения Можно найти в течение полиномиального времени решение, близкое к оптимальному. Алгоритм, возвращающий решения, близкие к оптимальным, называется приближенным алгоритмом. 18
Методы решения NP-полных задач Приближенные и эвристические методы – применение эвристик для выбора элементов решения. Псевдо полиномиальные алгоритмы – подкласс динамического программирования. Метод локальных улучшений – поиск более оптимального решения в окрестности некоторого текущего решения. Метод ветвей и границ - отбрасывание заведомо неоптимальных решений целыми классами в соответствии с некоторой оценкой. Метод случайного поиска – представление выбора последовательностью случайных выборов. 19
Спасибо за внимание! Вопросы? 20