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

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

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

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

4 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 – допустимое.

5 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 – допустимое.

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

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