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

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

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

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

NP-полнота задачи выполнимости
Определим наборы переменных:
1. Ci,j,t = 1 т.и.т.т., когда i-ая клетка на ленте машины M содержит символ Xj в момент времени t.
2. Sk,t = 1 т.и.т.т., когда M в момент времени t находится в состоянии qk.
3. Hi,t = 1 т.и.т.т., когда головка в момент t находится над i-ой клеткой
Свяжем эти переменные ограничениями, которые будут истинны только для M на w
Q0, Q1, …, Qq –такая, что Q0 – начальное, а Qq – допустимое.

NP-полнота задачи выполнимости
Утверждение о Q0, Q1, …, Qq равносильно следующему:
В каждом состоянии головка находится ровно над одной ячейкой
В каждом состоянии в каждой клетке ленты ровно один символ
Каждое состояние Qi, машина находится ровно в одном внутреннем состоянии
При одном переходе может изменится только та клетка, где головка
Изменение состояния происходит в соответствии с функцией переходов
Первое состояние является начальным
Последнее состояние - заключительное