Слайд 2NP-полнота задачи выполнимости
Задача выполнимости булевой функции:
Вход: булева функция, заданная формулой
Требуется определить, выполнима
![NP-полнота задачи выполнимости Задача выполнимости булевой функции: Вход: булева функция, заданная формулой](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/431773/slide-1.jpg)
ли функция, т.е. существует ли набор, на котором функция равно 1.
Теорема: Задача выполнимости булевой функции NP-полна.
Требуется доказать, что:
1. Эту задачу можно решить за полиномиальное время на НМТ.
2. Любую другую задачу класса NP можно свести к задаче выполнимости.
Слайд 3NP-полнота задачи выполнимости
1. Алгоритм на НМТ для задачи выполнимости:
1. Выбираем набор значений
![NP-полнота задачи выполнимости 1. Алгоритм на НМТ для задачи выполнимости: 1. Выбираем](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/431773/slide-2.jpg)
переменных
2. Вычисляем значение функции на данном наборе
Слайд 4NP-полнота задачи выполнимости
2. Сведение произвольного языка L∈NP к задаче выполнимости:
Пусть M∈НМТ, L(M)=L
Пусть
![NP-полнота задачи выполнимости 2. Сведение произвольного языка L∈NP к задаче выполнимости: Пусть](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/431773/slide-3.jpg)
входом M является слово w.
Покажем, как по M и w построить (за время, ограниченное полиномом) булеву функцию w0, выполнимую т. и т.т. когда M распознаёт w.
Т.к. M распознаёт w, то ∃ Q0, Q1, …, Qq – последовательность состояний M, такая, что Q0 – начальное, а Qq – допустимое.
Слайд 5NP-полнота задачи выполнимости
Определим наборы переменных:
1. Ci,j,t = 1 т.и.т.т., когда i-ая клетка
![NP-полнота задачи выполнимости Определим наборы переменных: 1. Ci,j,t = 1 т.и.т.т., когда](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/431773/slide-4.jpg)
на ленте машины M содержит символ Xj в момент времени t.
2. Sk,t = 1 т.и.т.т., когда M в момент времени t находится в состоянии qk.
3. Hi,t = 1 т.и.т.т., когда головка в момент t находится над i-ой клеткой
Свяжем эти переменные ограничениями, которые будут истинны только для M на w
Q0, Q1, …, Qq –такая, что Q0 – начальное, а Qq – допустимое.
Слайд 6NP-полнота задачи выполнимости
Утверждение о Q0, Q1, …, Qq равносильно следующему:
В каждом состоянии
![NP-полнота задачи выполнимости Утверждение о Q0, Q1, …, Qq равносильно следующему: В](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/431773/slide-5.jpg)
головка находится ровно над одной ячейкой
В каждом состоянии в каждой клетке ленты ровно один символ
Каждое состояние Qi, машина находится ровно в одном внутреннем состоянии
При одном переходе может изменится только та клетка, где головка
Изменение состояния происходит в соответствии с функцией переходов
Первое состояние является начальным
Последнее состояние - заключительное