Недетерминированная машина Тьюринга. Класс NP (два определения)

Машина Тьюринга состоит:

· Бесконечная лента

· Головка, которая двигается по ленте

· Программа МТ

Каждой паре 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:

· Задача коммивояжера

· Задача «об упаковке в контейнеры»