NP-полные задачи. Сложность задач Задачи формулируем как множества языков, распознаваемых МТ. То есть, на вход МТ подаётся «вопрос» и она отвечает «да» - презентация

1 NP-полные задачи

2 Сложность задач Задачи формулируем как множества языков, распознаваемых МТ. То есть, на вход МТ подаётся «вопрос» и она отвечает «да» (входное слово распознаётся) или «нет». Рассматриваем детерминированную машину Тьюринга (ДМТ) и недетерминированную (НМТ) Класс P – множество всех языков, допускаемых ДМТ с полиномиальной временной сложностью, т.е. {L | M ДМТ, полином p(n): временная сложность M оценивается полиномом p(n) и M распознаёт в точности L ( L(M)=L ) } Так же определяется класс NP для НМТ.

3 Пример задачи из класса NP Задача о клике: Вход: граф G(V,E), число k Требуется определить, содержит ли G клику (полный подграф) размером k. Алгоритм для НМТ: выбираем k вершин графа проверяем, что любые две вершины из выбранных соединены ребром

4 NP-полные задачи Определение. Язык L 0 NP называется полным для класса NP (NP-полным), если по M ДМТ, такому что L(M) = L 0, с временной сложностью T(n) и L NP можно эффективно построить M ДМТ, L(M) = L с временной сложностью T(p L (n)), где p L (n) – полином. Говорят, что L сводиться к L 0.

5 NP-полные задачи 1.Выполнимость булевой функции 2.Выполнимость КНФ 3.Выполнимость 3-КНФ 4.Клика размером k 5.Гамильтонов цикл в ориентированном графе 6.Вершинное покрытие k вершинами 7.Рёберное покрытие k рёбрами 8.Раскраска в k цветов 9.k вершин, разрезающих все циклы 10.k рёбер, разрезающих все циклы 11.Разбиение множества чисел на две части с равной суммой 12.Покрытие k множествами