'

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

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 5

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


Слайд 6

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


×

HTML:





Ссылка: