В детерминированной машине Тьюринга из каждой конфигурации имеется не более одного следующего шага. В недетерминированной машине для одной пары «символ–состояние» допускается несколько команд, поэтому вычисление образует дерево возможных ветвей. Слово принимается, если существует хотя бы одна принимающая
Класс \(P\) состоит из языков, распознаваемых детерминированными МТ за полиномиальное время, а \(NP\) — из языков, распознаваемых недетерминированными МТ за полиномиальное время. Очевидно, \(P\subseteq NP\)
Что важно запомнить
- Детерминированное вычисление задаёт единственную траекторию конфигураций.
- Недетерминированное вычисление допускает ветвление. Для принятия достаточно одной принимающей ветви.
- \(P\) задаётся полиномиальным распознаванием детерминированной МТ, а \(NP\) — недетерминированной
- Всегда \(P\subseteq NP\). Равенство этих классов из включения не следует.
Детерминированная и недетерминированная модели
У детерминированной МТ текущая конфигурация однозначно задаёт следующую. У НМТ одной паре «обозреваемый символ, состояние» может соответствовать несколько команд. Поэтому из одной конфигурации могут возникать несколько продолжений, а все вычисления на одном входе образуют ориентированное
НМТ принимает слово, если среди ветвей существует принимающее вычисление. Для отрицательного входа принимающей ветви быть не должно.
Класс P
В обозначениях курса \(P\) — класс языков, распознаваемых детерминированными машинами Тьюринга за полиномиальное время. Это формализация задач распознавания, для которых имеется эффективный детерминированный
Класс NP
\(NP\) — класс языков, распознаваемых недетерминированными МТ за полиномиальное время. Содержательно недетерминизм можно понимать как возможность «угадать» один из вариантов и затем проверить выбранную ветвь за полиномиальное число шагов.
Каждую детерминированную машину можно рассматривать как частный случай недетерминированной, поэтому \(P\subseteq NP\). В курсе далее показывается, что если хотя бы один NP-полный язык окажется в \(P\), то
Пример простыми словами
Для SAT недетерминированная машина может последовательно выбрать значения всех переменных, а затем проверить получившуюся КНФ. Если существует удовлетворяющий набор, одна ветвь выбора приведёт к принимающему состоянию. Это типичный способ увидеть принадлежность задачи классу NP.
Частые ошибки
- Думать, что НМТ должна проверить все ветви последовательно. В определении принятия достаточно существования одной принимающей ветви.
- Считать \(NP\) классом «неполиномиальных» задач. Буква N относится к недетерминированности, а не к отрицанию слова polynomial.
- Выводить из \(P\subseteq NP\), что \(P=NP\). Включение само по себе равенства не даёт.
