P * NP.

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

similar documents