(см. сложность) Элементы теории сложности алгоритмов и вычислений. Хахаян (2010) (1186152), страница 9
Текст из файла (страница 9)
В условии даны: множества городов, расстояния между ними и граница В; при этомспрашивается, существует ли проходящий через все городамаршрут длины, не превосходящей В. Полиномиальный алгоритм решения этой задачи не известен.
Предположим, однако,что относительно некоторой индивидуальной задачи кто-тополучил ответ «да». Если вы в этом сомневаетесь, то можнотребовать «доказательства» этого утверждения - предъявлениямаршрута, обладающего необходимыми свойствами. Имеяпредъявленное решение, нетрудно проверить, является ли онона самом деле маршрутом, и если это так, то вычислить егодлину, сравнить ее с границей В и тем самым проверитьсоответствующее утверждение. Более того, эту «процедурупроверки» можно представить в виде алгоритма, временнаясложность которого ограничена полиномом от Length [I].Другой пример задачи, которая обладает этим свойством,- задача ИЗОМОРФИЗМ ПОДГРАФУ из Главы 1. Пусть данаиндивидуальная задача I, в которой указаны два графа Gi=(VhEi) и G2=(V2, Ez>. Если ответом на вопрос задачи будет «да»,то этот факт можно «доказать», предъявив подмножества V с .VI и Е' с Ei и взаимно-однозначную функцию f.которые обладают необходимыми свойствами.
В этом случаеверность утверждения опять-таки может быть легкоустановлена за полиномиальное от Length[l] время путемпростой проверки того, что V', Е’ и / удовлетворяюттребованиям, сформулированным в задаче.Понятие полиномиальной проверяемости позволяетвыделить задачи класса NP. Отметим, что проверяемость заполиномиальное время не влечет разрешимости заполиномиальное время. Утверждая, что за полиномиальноевремяможнопроверитьответ «да» длязадачиКОММИВОЯЖЕР, мы не учитываем время, которое можетпонадобитьсянапоиск нужногомаршрутасредиэкспоненциального числа всех возможных маршрутов. Мылишь утверждаем, что по любому заданному маршруту дляиндивидуальной задачи I можно за полиномиальное времяпроверить, «доказывает» ли этот маршрут, что ответ на вопросотносительно индивидуальной задачи I есть «да».Неформально класс NP можно определить с помощьюпонятия, которое называется недетерминированным алгоритмом.
Такой алгоритм состоит из двух различных стадий стадии угадывания, и стадии проверки. По заданнойиндивидуальной задаче I на первой стадии происходит простоугадывание некоторой структуры S. Затем I и S вместеподаются в качестве входа на стадию проверки, котораявыполняется обычным детерминированным образом изаканчивается либо ответом «да», либо ответом «нет», либопродолжается бесконечно без остановки (позже увидим, чтопоследние две возможности различать не обязательно).Неформальное определение.Недетерминированныйалгоритмрешаетзадачураспознавания П, если для любой индивидуальной задачи 1 е£>п выполнены следующие два свойства:1.
Если Ie Yn, то существует такая структура S, угадываниекоторой для входа I приведет к тому, что стадия проверки,начиная работу на входе (I, S), закончится ответом «да».2. Если то I £ Yn, то не существует такой структуры S,угадывание которой для входа I обеспечило бы окончаниестадии проверки на входе (I,S) ответом «да».Недетерминированныйалгоритмрешения задачиКОММИВОЯЖЕР можно построить, используя в качествестадииугадыванияпростовыборпроизвольнойпоследовательности городов, а в качестве стадии проверки упомянутую выше полиномиальную процедуру «проверкадоказательства» для задачи КОММИВОЯЖЕР. Очевидно, длялюбой индивидуальной задачи I найдется такая догадка S, чторезультатом работы стадии проверки на входе (I,S) будет «да»в том и только в том случае, если для индивидуальной задачи Iсуществует маршрутискомой длины.Длялюбойиндивидуальной задачи I из КОММИВОЯЖЕР, ДЛЯКОТОРОЙ СУЩЕСТВУЕТ маршрут нужной длины, этотмаршрут и будет такой догадкой.
Если в индивидуальнойзадаче такого маршрута НЕ СУЩЕСТВУЕТ, то никакаядогадка не пройдёт стадию проверки с положительнымответом.Говорят,чтонедетерминированныйалгоритм,решающий задачу распознавания П, работает в течениеполиномиального времени, если найдется полином р такой,что для любого 1еГп найдется догадка S, приводящая настадии детерминированной проверки на входе (I, S) к ответу«да» за время p(Lenglh [I]) и «размер» угадываемой структурыS будет ограничен полиномом от Length [I].Таким образом, для любой индивидуальной задачи сположительным ответом, можно указать догадку, дающуюположительное решение, которую можно проверить заполиномиальное время от длины задачи.Класс NP, определяемый неформально, есть класс всех задач распознавания П, которые (при разумном кодировании)могутбытьрешенынедетерминированными(Nnondeterministic) алгоритмами за полиномиальное (Р polinomial) время.
Задача КОММИВОЯЖЕР принадлежитклассу NP. Доказательство аналогичного утверждения озадаче ИЗОМОРФИЗМ ПОДГРАФУ оставляем в качествеупражнения.В неформальных определениях термином «решает»следует пользоваться осторожно. Основное назначениеполиномиального недетерминированного алгоритма состоит вобъяснении понятия «проверяемость за полиномиальноевремя», а не в том, чтобы служить методом решения задачраспознавания свойств. При каждом входе такой алгоритмимеет не одно, а несколько возможных вычислений: поодному для каждой возможной догадки.Имеется еще одно важное отличие «решения» задачираспознавания недетерминированным алгоритмом от решениядетерминированным алгоритмом, а именно в первом случаеотсутствует симметрия между ответами «да» и «нет». Еслизадача: «Дано I; верно ли, что для I выполняется свойство XI»может быть решена полиномиальным детерминированнымалгоритмом, то такое же утверждение справедливо и длядополнительной задачи: «Дано I, верно ли, что для I невыполняется свойство X?».
Это следует из того, чтодетерминированный алгоритм останавливается при всехвходах, поэтому достаточно поменять местами ответы «да» и«нет» (переставить состояния qv и qNв ДМТ-программе).Совершенно не очевидно, что то же самое верно для всехзадач,разрешимыхзаполиномиальноевремянедетерминированными алгоритмами. Рассмотрим, например,дополнение задачи КОММИВОЯЖЕР: дано множествогородов, расстояния между ними и граница Я; верно ли, чтонет маршрута, проходящего через все города и имеющегодлину, не превосходящую В1 Для выяснения, имеет липоставленный вопрос ответ «да», не известен способ, которыйбыл бы короче, чем проверка всех (или почти всех)возможных маршрутов.
Другими словами, не известенполиномиальный недетерминированный алгоритм решенияэтой дополнительной задачи. Та же самая ситуация имеетместо для многих других задач из NP. Таким образом, принадлежность задачи П классу Р влечет принадлежность дополнительной задачи классу Р, но не известно, имеет ли место аналогичное утверждение для класса NP.Формализуем приведенное определение в терминахязыкови машинТьюринга (см.(1)).Формальнымэквивалентом недетерминированного алгоритма являетсяпрограмма для недетерминированной одноленточной машиныТьюринга (НДМТ).
Модель НДМТ имеет в точности такую жеструктуру, как ДМТ: отличие состоит лишь в том, что НДМТдополнена угадывающим модулем со своей головкой, котораяможет только записывать на ленту (см. рис. З.1.).Угадывающий модуль дает информацию для записывания«догадки» и применяется только с этой целью.3.1 Схематическое представление недетерминированнойодноленточной машины Тьюринга (НДМТ).Программа дляНДМТ,илиНДМТ-программа,определяется точно так же, как ДМТ-программа, при этомиспользуются: ленточный алфавит Г, входной алфавит 2’,пустой символ Ъ, множество состояний Q, начальноесостояние qo, заключительные состояния qv и qN, функцияперехода <5:ш \ { ^ , ? 4 ) х г ^ а х г х н . + 1}Вычисление НДМТ-программы при входе х е 2* вотличие от вычисления ДМТ-программы имеет две различныестадии.
На первой стадии происходит «угадывание». Вначальный момент времени входное слово х записывается вячейках с номерами 1 , 2 ,|х| (остальные ячейки пусты),читающая/пишущая головка «смотрит» на ячейку с номером1 , пишущая головка угадывающего модуля смотрит на ячейкус номером 1, а устройство управления пассивно. Затемугадывающий модуль начинает управлять угадывающейголовкой, которая делает один шаг в каждый момент времении либо пишет в находящейся под ней ячейке одну из буквалфавита Г и сдвигается при этом на одну ячейку влево, либоостанавливается. В последнем случае угадывающий модульпереходит в пассивное состояние, а управляющее устройствоначинает работу в состоянии q 0. Угадывающий модульрешает, продолжить ли работу, перейти ли в пассивноесостояние, какую букву из Г написать на ленте, причем делаетэто совершенно произвольно.
Таким образом, угадывающиймодуль до момента окончания своей работы может написатьлюбое слово из Г* и в действительности может никогда неостановиться.Стадия проверки начинается в тот момент, когдауправляющее устройство переходит в состояние q0. Начиная сэтогомомента,вычислениеНДМТ-программыосуществляется в точности по тем же правилам, что и ДМТпрограммы. Угадывающий модуль и его головка ввычислении больше не участвуют, выполнив свою роль, т. е.записав на ленте слово-догадку.. Конечно, слово-догадкаможет просматриваться читающей/пишущей головкой впроцессе проверки.
Вычисление заканчивается тогда, когдауправляющее устройство перейдет в одно из двухзаключительных состояний q Y или qN ; это состояниеназывается принимающим, если остановка происходит всостоянии qy. Все остальные вычисления, которыезаканчиваются или нет, называются непринимающими.Отметим, что любая НДМТ-программа М может иметьбесконечное число возможных вычислений при данном входех, по одному для каждого слова-догадки из Г*.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
