Машина Тьюринга состоит:
· Бесконечная лента
· Головка, которая двигается по ленте
· Программа МТ
Каждой паре q(i)a(j) ставится в соответствии q(k)a(s)d(r) (d - направление), причем однозначно (свойство детерминированности)
НМТ: каждой паре q(i)a(j) ставится в соответствии множество троек:
Заранее невозможно сказать по какому правилу пойдет. В каждой момент некоторым образом выбирается одна тройка из множества.
Условие задачи: выбирать вариант, который приведет к правильному решению. Необходимо, чтобы какой-то механизм подсказывал для выбора правильного варианта.
Механизм должен показать цепочку, чтобы был правильный результат.
Определение класса NP:
1. Задача Т принадлежит классу NP, если Т может быть решена за полиномиальное время на НМТ.
NP– недетерминированный, полиномиальное время.
2. Задача T , если ее можно подставить в виде: , где q() –полином; R(x,y) ; y- дополнительные данные.
Пример задач, принадлежащих классу NP:
· Задача коммивояжера
· Задача «об упаковке в контейнеры»