Детерминированные машины Тьюринга и класс P
Для того чтобы формализовать понятие алгоритма, необходимо зафиксировать определённую модель процесса вычислений. Такой моделью у нас будет служить детерминированная одноленточная машина Тьюринга (ДМТ). От рассмотренной нами ранее МТ данная модель отличается тем, что машина может завершить свою работу, только оказавшись в одном из двух состояний qY или qN.
В первом случае считается, что результатом работы ДМТ будет ответ “да”, а во втором – ответ “нет”.
Соответствие между распознаванием языков и решением задач распознавания определяется следующим образом. Будем говорить, что ДМТ-программа M решает задачу распознавания П при кодировании e, если M останавливается на всех словах, составленных из букв входного алфавита и LM = 
.
Определим понятие «временна՛я сложность». Время, требуемое ДМТ с программой М, для вычисления при входе x, есть число шагов, выполняемых до момента остановки. Если программа M останавливается на всех входах x из 
, то временну՛ю сложность TM этой программы можно определить как функцию 
:
TM (n)=max{ m: существует такое слово 
, имеющее длину | x |= n, что вычисление программой M при входе x требует время m }.
Детерминированная программа M называется полиномиальной ДМТ программой, если существует такой полином p, что для всех 
, TM (n)≤ p (n). Теперь формально можно определить класс языков P. P = {L: существует полиномиальная ДМТ программа M такая, что L = LM }. Определение означает, что задача распознавания 
при кодировании e, если 
, т.е. существует полиномиальная ДМТ программа, которая решает задачу П при кодировании e. Учитывая рассуждения об эквивалентности разумных кодировок, мы обычно не будем приводить конкретные схемы кодирования, а будем просто говорить, что задача распознавания .
Термин «полиномиальный алгоритм» часто также будем использовать неформально. Формальным эквивалентом полиномиального алгоритма является полиномиальная ДМТ программа, однако в дальнейшем, учитывая замечание об эквивалентности различных моделей вычислений относительно полиномиального времени работы, мы можем формальное определение класса P сформулировать в терминах любой из указанных моделей, в любом случае получим один и тот же класс. Таким образом, при доказательстве того, что определяемые задачи могут быть решены полиномиальным алгоритмом, у нас нет необходимости вдаваться в детали ДМТ. На самом деле, следуя общепринятой практике, мы будем обсуждать алгоритмы в машинно-независимом стиле, т.е. мы будем рассматривать их работу непосредственно с компонентами индивидуальной задачи, а не с их кодами.
Недетерминированное вычисление и класс NP
Сначала поясним смысл понятия, лежащего в основе определения класса NP.
Рассмотрим задачу КОММИВОЯЖЁР. Полиномиальный алгоритм этой задачи неизвестен. Предположим, однако, что для некоторой индивидуальной задачи каким-то образом был получен ответ “да”. Чтобы удостовериться в правильности ответа необходимо иметь маршрут, обладающий необходимыми свойствами. Имея этот маршрут, легко проверить, является ли он маршрутом, определить его длину, сравнить её с границей B, проверить высказанное утверждение. Эту процедуру проверки можно ограничить полиномом Length (I). Именно понятие полиномиальной проверяемости позволяет выделить задачи класса NP. Отметим, что проверяемость за полиномиальное время не влечёт разрешимости за полиномиальное время. Неформально класс NP можно определить понятием «недетерминированный алгоритм». Такой алгоритм состоит из двух стадий: стадии угадывания и стадии проверки.
По заданной индивидуальной задаче I на первой стадии происходит угадывание некоторой структуры S. Затем пара (I, S) подаётся в качестве входа на стадию проверки. Работа на этой стадии осуществляется обыкновенным детерминированным образом, в результате работы либо получается ответ “да”, либо ответ “нет”, либо вычисление продолжается бесконечно. Таким образом, недетерминированный алгоритм решает задачу распознавания П, если для любой индивидуальной задачи 
выполняются следующие два условия:
1.Если 
, то существует такая структура S, угадывание которой для входа I приведёт к тому, что стадия проверки, начиная работу на входе (I, S), заканчивает работу ответом “да”.
2.Если 
, то не существует такой структуры S, угадывание которой для входа I обеспечивало бы окончание стадии проверки на входе (I, S) ответом “да”.
Например, недетерминированный алгоритм задачи КОММИВОЯЖЁР, можно сформулировать следующим образом: на стадии угадывания формируемая структура S представляет собой некоторый маршрут, содержащий все города из списка; на стадии проверки подсчитывается длина маршрута и сравнивается с границей B.
Говорят, что недетерминированный алгоритм решает задачу распознавания П, работая в течение полиномиального времени, если найдётся такой полином p, что для любой найдётся некоторая догадка S, приводящая на стадии детерминированной проверки на входе (I,S) к ответу “да” за время p(Length(I)).
Замечание: из определения следует, что размер угадываемой структуры S будет обязательно ограничен полиномом от Length(I) по длине кода.
Класс NP – это класс всех задач распознавания П, которые при разумном кодировании могут быть решены недетерминированными алгоритмами за время, ограниченное полиномом p. Фактически, класс NP содержит задачи, правильность ответов которых можно проверить за полиномиальное время.
Имеется важное отличие классов P и NP.
Для класса P имеется симметрия между ответами “да” и “нет”, т.е. если задача I имеет вид: “ Дано I, верно ли что для I выполнимо свойство x ”. Если эта задача решаема за полиномиальное время, то за полиномиальное же время будут решаться и дополнительные задачи имеющий вид: “ Дано I, верно ли что для I условие x не выполняется ”.
Для задач класса NP исходная задача, принадлежащая классу NP, может породить дополнительную задачу, классу NP не принадлежащую.