(см. сложность) Элементы теории сложности алгоритмов и вычислений. Хахаян (2010) ((см. сложность) Элементы теории сложности алгоритмов и вычислений. Хахаян (2010).pdf), страница 10

Будемговорить, что НДМТ-программа М принимает х, если покрайней мере одно из ее вычислений на входе х являетсяпринимающим. Язык, распознаваемый программой М естьязык^ м ~~ ^ е S , М принимает #}, Время, требующеесянедетерминированной программе М для того, чтобы принятьслово х е Ьм, есть минимальное число шагов, выполняемых настадиях угадывания и проверки до момента достижениязаключительного состояния qY, где минимум берется по всемпринимающим вычислениям программы М на входе х.Временная сложность НДМТ-программы М есть функцияТЛ1: Z —*Z~, определяемая следующим образом:/(ГД( ( я } = т а х 1 {1 } jj ч т :хIсуществует хе= LM, |х | —такое, что время принятиях У 1 .программой М равно m'/Временная сложность программы М зависит только отчисла шагов, выполняемых в принимающих вычислениях.

Мыполагаем М(п) равным 1, если нет ни одного входа длины п,принимаемого программой М.НДМТ-программа называется НДМТ-программой сполиномиальным временем работы, если найдется полином ртакой, что Тfjp) < р(п) для всех п > 1. Наконец, класс NPформально определяется так:Установим взаимосвязь между этими формальнымиопределениямии предшествующиминеформальными.Единственный момент, который следует специальнооговорить, состоит в следующем. Если недетерминированныйалгоритм угадывает структуру S, зависящую от условиярассматриваемой задачи, то угадывающий модуль НДМТ,напротив, полностью игнорирует входное слово. Хотя любоеслово из Г* может быть получено в результате работыугадывающего модуля, НДМТ-программу всегда можносконструировать так, что стадия проверки будет начинаться спроверки того, соответствует ли догадка подходящейструктуре для заданного входа.

Иначе программа может сразуже перейти в заключительное состояние qN.Будем говорить, что задача распознавания принадлежитклассу NP при схеме кодирования е, если L[n,e]e NP. Как и вслучае класса Р, мы будем просто говорить, что П лежит в NP.В заключение заметим, что наши формальныеопределения можно было бы перефразировать для любойдругой стандартной модели вычислительного устройства. Т.к.все такие модели эквивалентны с точностью додетерминированных полиномиальных вычислений, всеполучаемые при этом версии класса NP будут идентичны.Итак, правомерно сделанное ранее предложение отождествитьформально определенный класс NP с классом всех задач рас­познавания, разрешимых недетерминированными алгоритма­ми с полиномиальным временем работы.Перед определением третьего, самого важного класса класса NP-полных задач, мы обсудим взаимоотношениямежду классами Р и NP.ВЗАИМООТНОШЕНИЕ МЕЖДУ КЛАССАМИ Р И NPВопрос о взаимоотношении классов Р и NP имеет фунда­ментальное значение для теории NP-полных задач.

Одно соот­ношение, до настоящего момента явно не сформулированное,заключается в том, что P c NP. Всякая задача распознавания,разрешимая за полиномиальное время детерминированнымалгоритмом, разрешима также за полиномиальное времянедетерминированным алгоритмом. Чтобы убедиться в этом,достаточно заметить, что любой детерминированныйалгоритм может быть использован в качестве стадии проверкинедетерминированного алгоритма. Если П еР и АпроизвольныйдетерминированныйполиномиальныйалгоритмрешенияП,тополиномиальныйнедетерминированный алгоритм для П можно получить,воспользовавшись А в качестве стадии проверки и игнорируястадию угадывания.

Таким образом, из П еР следует, чтоneN P.Есть много причин считать это включением строгим.Полиномиальныенедетерминированныеалгоритмыопределеннооказываютсяболеемощными,чемполиномиальные детерминированные алгоритмы и не из­вестны общие методы их превращения в детерминированныеполиномиальные алгоритмы. В действительности самыйсильный из известных результатов состоит в следующем:Теорема 3.1. Если Пе NP, то существует такойполином р, что П может быть решена детерминированнымалгоритмом с временной сложностью 0(2р(п)).Доказательство. Пусть ^-полиномиальный недетерминиро­ванный алгоритм решения задачи П и q(n) - полином, ограни­чивающий временную сложность алгоритма А(безограничения общности можно считать, что q может бытьвычислен за полиномиальное время; этого можно добиться,взяв, например, q(n) = С\п при достаточно большихконстантах С\ и с.)По определению класса NP, для каждого принимаемоговхода длины п найдется некоторое слово-догадка (в алфавитеГ символов ленты) длины не более q(n), такое, что в алгоритмеА стадия проверки дает при этом входе ответ «да» не болеечем за q(n) шагов.

Общее число догадок, которые нужнорассмотреть, не превосходит кч(п), где к - \Д (если словодогадка короче q(n), то его можно дополнить пустымисимволами и рассматривать как слово длины q(n)).Теперь можно детерминированным образом выяснить,имеет ли алгоритм А на заданном входе длины ппринимающее вычисление. Для этого достаточно на каждойиз кч(п> возможных догадок запустить детерминированнуюстадию проверки алгоритма А и позволить ей работать до тогомомента, пока она не остановится или не сделает q(n) шагов.Этот моделирующий алгоритм даст ответ «да», если емувстретится слово-догадка, приводящее к принимающемувычислению длины не более q(n), и ответ «нет» в противномслучае.Такойалгоритмбудетдетерминированнымалгоритмом решения задачи П.

Его временная сложностьравна q{n)-kq(nj и хотя это экспонента, но при подходящемвыборе полинома р сложность не превосходит 0{2р(п>).Процесс моделирования, предложенный в доказательствеТеоремы 3.1 можно ускорить с помощью метода ветвей играниц или с помощью более тщательного перебора, когдаизбегаются, очевидно, ненужные слова-догадки. Но неизвестен метод, осуществляющий такое моделированиебыстрее, чем за экспоненциальное время.Способностьнедетерминированногоалгоритмапроверить за полиномиальное время экспоненциальное числовозможностей может навести на мысль, что полиномиальныенедетерминированные алгоритмы являются более мощнымсредством,чемполиномиальныедетерминированныеалгоритмы.

Для многих частных задач класса NP, таких, какКОММИВОЯЖЕР, ИЗОМОРФИЗМ ПОДГРАФУ и многихдругих не найдено полиномиального детерминированногоалгоритма, несмотря на упорные усилия многих известныхисследователей.Не удивляет поэтому широко распространенное мнение,что P^NP, хотя пока доказательство этой гипотезыотсутствует.Рис.

3.2 Гипотетическая картина класса NP.Скептик может сказать, что неудача в доказательствегипотезы P^NP является столь же сильным аргументом впользу соотношения Р = NP, как и неудача в поиске соответ­ствующихполиномиальных алгоритмов в пользупротивоположного ему утверждения. Задачи всегда кажутсятруднорешаемыми, пока не найдены эффективные алгоритмыих решения.

Но при существующем в настоящее времяуровне знаний, по-видимому, более разумно работать присоглашении P*NP, чем пытаться доказать противоположное.На основе накопленного опыта мы будем представлять себекласс NP так, как он изображен на рис. 3.2, ожидая, чтозатененная область, обозначающая NP\P, не пуста.ГЛАВА 4.

ПОЛИНОМИАЛЬНАЯ СВОДИМОСТЬ И NPПОЛНЫЕ ЗАДАЧИЕсли Р не совпадает с NP, то различие между Р и NPYPочень существенно. Все задачи из Р могут быть решены поли­номиальными алгоритмами, а все задачи из NP\Pтруднорешаемы. Поэтому, если P^NP, то для каждойконкретной задачи Пе NP важно знать, какая из двухвозможностей реализуется.Конечно, пока не доказано, что P^NP, нет никакойнадежды показать, что некоторая конкретная задачапринадлежит классу NP\P. По этой причине цель теории NPполных задач заключается в доказательстве более слабыхрезультатов вида: если P^NP, то Пе NP\P.

Хотя доказа­тельство таких условных результатов может показаться стольже трудным, как и безусловных, но имеются несложныеметоды доказательства. Такие условные результаты можнорассматривать как подтверждение труднорешаемости с той жестепенью уверенности, с какой мы считаем, что класс Ротличается от NP.Основная идея условного подхода основана на понятииполиномиальной сводимости. Будем говорить, что имеетместо полиномиальная сводимость языка L2cE * \ к языку Ь2сХ*2 , если существует функция f. Е*[—>Е*2, удовлетворяющая,двум условиям:1.

Существует ДМТ-программа, вычисляющая / с временнойсложностью, ограниченной полиномом.2. Для любого хе 27*/, хе Lh в том и только в том случае, еслиf(x)e L2.Если L] полиномиально сводится к Ь2, то будем писать L/ 'X L2и говорить «Тi сводится к Ь2» (опуская слово«полиномиально»). Важность понятия полиномиальнаясводимость вытекает из следующей леммы:Лемма 4.1.

Если L i ^ L 2, то из L2е Р следует, что L i e Р.{Эквивалентное утверждение: из L jg Р следует, что L2 0 Р).Доказательство. Пусть 27; и Е2 - алфавиты языков Д и Ь2соответственно, функция/: 27/—*Е2осуществляет полиномиаль­ную сводимость Li к L2. Пусть М, - полиномиальная ДМТпрограмма, вычисляющая f и М2 :— полиномиальная ДМТпрограмма, распознающая Ь2.

Полиномиальная ДМТпрограмма, распознающая Z/, может быть полученакомпозицией программы М/ и М2. Ко входу х е 27*/ вначалеприменяется Mi, чтобы построить Д х)е 27*2. Затем к f(x)применяется программа М2, выясняющая, верно ли, что f(x) еL2. Поскольку хе Lj тогда и только тогда, когда/(х)е Ь2, то этоописание дает ДМТ-программу, распознающую Lt. То, чтовремя работы этой программы ограничено полиномом,немедленно следует из полиномиальности программ Mi и М.Точнее, если pi и р2 - полиномы, ограничивающие времяработы программ Mi и М2 соответственно, то \f(x)\ < £>/(|х[).