Класс NP и NP-полные задачи. NP-полнота задачи выполнимости Задача выполнимости булевой функции: Вход: булева функция, заданная формулой Требуется определить,

Презентация:



Advertisements
Похожие презентации
NP-полнота Теорема Кука. Полиномиальная сводимость Пусть Π 1 =(X 1,Y 1 ) и Π 2 =(X 2,Y 2 ) задачи распознавания. Будем говорить, что Π 1 полиномиально.
Advertisements

NP-полные задачи. Сложность задач Задачи формулируем как множества языков, распознаваемых МТ. То есть, на вход МТ подаётся «вопрос» и она отвечает «да»
NP-полнота Основные NP-полные задачи. Задача «Независимое множество» Условие. Задан граф G=(V,E) и целое число k. Вопрос. Существует ли независимое множество.
Линейное программирование Задача о покрытии. Задача «Покрытие» Дано: Совокупность U из n элементов, и набор подмножеств U, Ω = {S 1,…, S k }, и веса(стоимости)
Алгоритм называется частичным алгоритмом, если мы получаем результат только для некоторых d є D и полным алгоритмом, если алгоритм получает правильный.
Линейное программирование Задача о покрытии. Задача «Покрытие» Дано: Совокупность U из n элементов, и набор подмножеств U, Ω = {S 1,…, S k }, и веса(стоимости)
Основные понятия теории NP-полноты P NP?. Задачи распознавания свойств Класс задач распознавания свойств (ЗРС) – множество проблем, решением которых является.
Приближенные схемы Задачи упаковки. Задача oб упаковке Дано: n предметов и их размеры a 1,…,a n (0,1]. Найти упаковку всех предметов в единичные ящики,
Введение в формальные (аксиоматические) системы. Формальные системы - это системы операций над объектами, понимаемыми как последовательность символов.
Приближенные схемы Задачи теории расписаний. Полиномиальная приближенная схема (PTAS) Семейство приближенных алгоритмов для задачи Π, {A ε } ε называется.
Классификация задач по классам сложности Классификация задач по классам сложности – (P-сложные, NP-сложные, экспоненциально сложные и др.).P-сложныеNP-сложные.
Машина Тьюринга. КТО? Машина Тьюринга – математическая (воображаемая) машина, а не машина физическая. Она такой же математический объект, как функция,
Приближенные схемы Задачи теории расписаний. Полиномиальная приближенная схема (PTAS) Семейство приближенных алгоритмов для задачи Π, {A ε } ε называется.
Теория Автоматов Конечные функциональные преобразователи Конечные функциональные преобразователи.
Каждое составное высказывание можно выразить в виде формулы, в которую входят логические переменные, обозначающие высказывания, и знаки логических операций,
3. Нормальные формы логических функций Нормальной формой логической функции является такая формула, которая считается наиболее наглядной и удобной в использовании,
Комбинаторные алгоритмы Задача о покрытии. Задача о покрытии множествами Дано: Совокупность U из n элементов, и набор подмножеств U, S = {S 1,…, S k },
LOGO Определение машины Тьюринга. Машина Тьюринга – абстрактный исполнитель, осуществляющий алгоритмический процесс Это математический объект, а не физическая.
ССОД НГТУНГТУ Метод существенных путей Для того, чтобы неисправность была обнаружена на внешнем выходе объекта, необходимо и достаточно, чтобы 1.неисправность.
Алгоритм Эдмондса Лекция 11. Идея алгоритма Эдмондса Пусть есть некоторое паросочетание M, построим M-чередующийся лес F. Начинаем с множества S вершин.
Транксрипт:

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

NP-полнота задачи выполнимости Задача выполнимости булевой функции: Вход: булева функция, заданная формулой Требуется определить, выполнима ли функция, т.е. существует ли набор, на котором функция равно 1. Теорема: Задача выполнимости булевой функции NP-полна. Требуется доказать, что: 1. Эту задачу можно решить за полиномиальное время на НМТ. 2. Любую другую задачу класса NP можно свести к задаче выполнимости.

NP-полнота задачи выполнимости 1. Алгоритм на НМТ для задачи выполнимости: 1. Выбираем набор значений переменных 2. Вычисляем значение функции на данном наборе

NP-полнота задачи выполнимости 2. Сведение произвольного языка L NP к задаче выполнимости: Пусть M НМТ, L(M)=L Пусть входом M является слово w. Покажем, как по M и w построить (за время, ограниченное полиномом) булеву функцию w 0, выполнимую т. и т.т. когда M распознаёт w. Т.к. M распознаёт w, то Q 0, Q 1, …, Q q – последовательность состояний M, такая, что Q 0 – начальное, а Q q – допустимое.

NP-полнота задачи выполнимости Определим наборы переменных: 1. C i,j,t = 1 т.и.т.т., когда i-ая клетка на ленте машины M содержит символ X j в момент времени t. 2. S k,t = 1 т.и.т.т., когда M в момент времени t находится в состоянии q k. 3. H i,t = 1 т.и.т.т., когда головка в момент t находится над i-ой клеткой Свяжем эти переменные ограничениями, которые будут истинны только для M на w Q 0, Q 1, …, Q q –такая, что Q 0 – начальное, а Q q – допустимое.

NP-полнота задачи выполнимости Утверждение о Q 0, Q 1, …, Q q равносильно следующему: 1.В каждом состоянии головка находится ровно над одной ячейкой 2.В каждом состоянии в каждой клетке ленты ровно один символ 3.Каждое состояние Q i, машина находится ровно в одном внутреннем состоянии 4.При одном переходе может изменится только та клетка, где головка 5.Изменение состояния происходит в соответствии с функцией переходов 6.Первое состояние является начальным 7.Последнее состояние - заключительное

NP-полнота задачи о клике Лемма: Задача выполнимости булевой функции, находящейся в КНФ, полна. Теорема: Задача о клике NP-полна. Требуется доказать, что задача КНФ-выполнимости булевой функции полиномиально трансформируема в задачу о клике.