Лекция 5 Детерминированные машины Тьюринга и класс p

Для того, чтобы формализовать понятие алгоритма, необходимо зафиксировать определённую модель процессов вычислений. Такой моделью у нас будет служить детерминированная одноленточная машина Тьюринга (ДМТ). От рассмотренной нами ранее МТ данная модель отличается тем, что машина может завершить свою работу, только оказавшись в одном из двух состояний qY или qN.

В первом случае считается, что результатом работы ДМТ будет ответ “да”, а во втором – ответ “нет”.

Соответствие между распознаванием языков и решением задач распознавания определяется следующим образом. Будем говорить, что ДМТ - программа M решает задачу распознавания П при кодировании e, если M останавливается на всех словах, составленных из букв входного алфавита, и L_M=.

Определим понятие «временная сложность». Время, требуемое ДМТ с программой М для вычисления при входе x, есть число шагов, выполняемых до момента остановки. Если программа M останавливается на всех входах x из , то временную сложность T_M этой программы можно определить как функцию :

T_M(n)=max{m: существует такое слово , имеющее длину |x|=n, что вычисление программой M при входеx требует время m}.

Детерминированная программа M называется полиномиальной ДМТ- программой, если существует такой полином p, что для всех ,T_M(n)≤p(n). Теперь формально можно определить класс языков P. P = {L: существует полиномиальная ДМТ–программа M такая, что L=L_M}. Определение означает, что задача распознавания, при кодировании 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 выполнимо свойство x”. Если эта задача решаема за полиномиальное время, то за полиномиальное же время будут решаться и дополнительная задача, имеющая вид: “Дано I, верно ли что для I условие x не выполняется”.

Для задач класса NP исходная задача, принадлежащая классу NP, может породить дополнительную задачу, классу NP не принадлежащую.