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

д. Во второй части в терминах условияформулируется вопрос, предполагающий один из двух ответов- «да» или «нет». Это описание определяет множества Du иYn очевидным образом. Индивидуальная задача принадлежитDn в том и только в том случае, когда она может бытьполучена из стандартной формы описания подстановкойконкретных значений во все компоненты условия.Индивидуальная задача принадлежит Yn в том и только в томслучае, когда ответом на вопрос задачи будет «да».Рассмотрим пример.ИЗОМОРФИЗМ ПОДГРАФУУСЛОВИЕ. Заданы два графа: Gj=(V/,Ej) и G2=(V2,E2).ВОПРОС. Верно ли, что G; содержит подграф, изоморфныйG-jl Другими словами, существуют ли:(1) подмножества C cCj и Е'аЕ] такие, что |F| = \V2\, |Е'| = \Е2\ и(2) взаимно однозначная функция / : V2-*F , такая, что (и,v} еЕ2 тогда и только тогда, когда {/{и), fly)} е Е'1Задача распознавания, соответствующая задаче окоммивояжере, может быть сформулирована следующимобразом.КОММИВОЯЖЕРУСЛОВИЕ.

Заданы конечное множество С = {cj, с2, ....ст}«городов», «расстояния» d{ch с;)е Z для каждой пары городовс„ с,еС и граница BeZ* (здесь 2? обозначает положительныецелые числа).ВОПРОС. Существует ли «маршрут», проходящий через всегорода из С, длина которого не превосходит В1 Другимисловами, существует ли последовательность <cv;/,c^2>---.c^o>элементов С, такая, чтоm-i^ ^ ( C«f/i* Cn(f-H)) + CK Cnimy °n (li)Второй пример служит также для иллюстрации важногоприемаполученияизоптимизационнойзадачисоответствующейзадачираспознавания.Есливоптимизационной задаче среди всех структур данного типаищется структура, имеющая минимальную «стоимость»(например, среди всех маршрутов ищется маршрутминимальной длины), то этой задаче можно сопоставитьзадачу распознавания, в которой в качестве дополнительногопараметра фигурирует числовая граница В, а вопрос ставитсяо существовании структуры данного типа, стоимость которойне превосходит В (например, маршрут длины не более В).Аналогичным образом задача распознавания может бытьполучена из задачи максимизации.

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

Для этогонужно только найти маршрут минимальной длины, вычислитьего длину и сравнить ее с заданной границей В. Т.к.КОММИВОЯЖЕР есть NP-полная задача, то отсюда следует,что и оптимизационная задача о коммивояжере столь жесложна. Таким образом, хотя в теории NP-полных задачрассматриваются только задачи распознавания, выводы этойтеории вполне применимы к задачам оптимизации.Теория NP-полных задач ограничивается толькозадачами распознавания. Это объясняется тем, что задачираспознавания имеют очень естественный формальныйэквивалент, удобный для изучения методами теориивычислений. Этот эквивалент называется «языком» иопределяется следующим образом.Для любого £ (алфавита) обозначим через £* множествовсех слов, составленных из символов алфавита £.

Например,если £ = {0, 1}, то £* состоит из пустого слова, а также слов О,1, 00, 01, 10, 11, 000, 001 и всех других конечных слов,состоящих из нулей и единиц. Любое подмножество Lcr£*будем называть языком в алфавите £. Таким образом,множество {01,001,111,1101010} является языком в алфавите0, 1. Языками также являются множество двоичных записейквадратов целых чисел, само множество {0, 1} и т.д.Соответствие между задачами распознавания и языкамиустанавливается с помощью схем кодирования, которыеприменяются для представления индивидуальной задачи.Напомним, что схема кодирования е задачи П описываеткаждую индивидуальную задачу из П подходящим словом внекотором фиксированном алфавите £.

Таким образом, задачаП и схема кодирования е задачи П разбивают слова из £* натри класса: слова, не являющиеся кодами индивидуальныхзадач из Г1; слова, являющиеся кодами индивидуальных задачиз П с отрицательным ответом на вопрос, и слова,являющиеся кодами индивидуальных задач из П сположительным ответом на вопрос. Третий класс слов и естьтот язык, который ставится в соответствие задаче П при коди­ровании е и обозначается через ЦП,е]:т42*',S есть алфавит схемы кодирования в,а х —код индивидуальной задачи/ е К п при схеме кодирования еПри применении формальной теории NP-полноты кзадачам распознавания будем говорить, что некоторыйрезультат имеет место для задачи П при схеме кодирования е,если этот результат имеет место для языка ЦП, е\.Следуя общепринятой практике, мы не всегда будемсоблюдать все эти формальности.

Если ограничиться только«разумными схемами кодирования», то при введении любогонового понятия или свойства, которое формулируется втерминах языка, оно не будет зависеть от способакодирования. Другими словами, если е и е' любые дверазумные схемы кодирования задачи П, то рассматриваемоесвойство языков ЦП,е] и ЦП,е'] выполняется (или невыполняется) для них одновременно. Это позволяет говоритьнеформально о том, что рассматриваемое свойство для задачиП выполняется или не выполняется.

Но при использованииэтого соглашения будем подразумевать, что можно указатьсхему кодирования е, что рассматриваемое свойствовыполняется для языка ЦП, е].Если вести изложение в стиле, не зависящем откодирования, то теряется связь с формальным понятием«длина входа». Поэтому необходим некоторый параметр,через который можно выразить временную сложность.Удобно считать, что с каждой задачей распознавания связанане зависящая от схемы кодирования функция Length: Dn —>Z\которая«полиномиально эквивалентна» длинекодаиндивидуальной задачи, получаемой при любой разумнойсхемекодирования.Полиномиальнаяэквивалентностьпонимается в следующем смысле: для любой разумной схемыкодирования е задачи П существуют два полинома р и р \такие, что если Is В и слово х есть код индивидуальной задачиI при кодировании е, то Length [1]< /;(|х|) и |х|< p\Length[I]), где|х| - длина слова х.

Например, в задаче ИЗОМОРФИЗМПОДГРАФУ можно положитьL en gth [/] — | V ,} - f I v%J; с г= ( у г £ г) и G 2= ( V 2JE 2)будутграфами,образующимирассматриваемуюиндивидуальную задачу. В задаче КОММИВОЯЖЕР можноположитьLength [/]«*« + riog2B“] + max{flogjrf {ct, c,}*"!; ct, c;eC).Так как любые две разумные схемы кодирования задачи Пдают полиномиально эквивалентные длины входов, тодиапазон для выбора функции L e n g t h очень широк, аполучаемые результаты будут верны для любой функцииL e n g th ,удовлетворяющейсформулированнымвышеусловиям.Отсутствие формального определения разумной схемыкодирования вызывает неудобства. Для преодоления этихнеудобств можно потребовать, чтобы условие задачи всегдасостояло из фиксированного набора основных теоретико­множественных объектов.

Мы не будем здесь накладыватьэтого требования. Однако дадим краткое описание одного изспособов определения стандартной схемы кодирования.Эта стандартная схема кодирования отображаетиндивидуальные задачи в правильно построенные слова(ППС) в алфавите у = {0, 1, —ППС определяетсярекурсивно:(1) Двоичная запись целого числа к , рассматриваемая какслово, состоящее из нулей и единиц (со знаком « - » передсловом, если к отрицательно), есть ППС, представляющеецелое число к .(2) Если х есть ППС, представляющее целое число к , то [х]есть ППС, которое может использоваться как «имя»(например, «имя» вершины графа, элемента множества илигорода в задаче о коммивояжере).(3) Если хI, х 2, ..

. , х т - правильно построенные слова,представляющие объекты Хь Х2,...,Хт, то ( х /, х 2, . . . , х т) естьППС, представляющее последовательность < Хь Х2,...,Хт >.Для указания схемы кодирования конкретной задачираспознавания, представленнойстандартной записью,заметим, что если каждая компонента условия представленанекоторым ППС, то все условия можно закодировать,пользуясь правилом (3). Таким образом, достаточно указатьспособ кодирования объекта каждого типа. При этом мыограничимся целыми числами, «элементами без структуры»(вершины графа, элементы множества, города и т. д.),последовательностями, множествами, графами, конечнымифункциями и рациональными числами.Правила (1) и (3) указывают, как кодировать целые числаи последовательности. Для кодирования элементов безструктуры присвоим им, согласно правилу (2), различные«имена», соблюдая при этом следующее условие: еслииндивидуальная задача содержит не более N элементов безструктуры, то используются имена, величина которых непревосходит N.

Объекты остальных четырех типовкодируются следующим образом.Множество объектов представляется в виде произвольноупорядоченной последовательности <ХЬ Х2,...,ХШ> элементовэтого множества и кодируется ППС, соответствующим этойпоследовательности.Граф с множеством вершин V и множеством ребер Екодируется ППС (х, у), где х н у есть ППС, представляющиемножества V и Е соответственно (элементами Е являютсядвухэлементные подмножества V, образующие ребра).Конечная функция f \ { щ , U 2, .. ., u m } —* W кодируется ППС((х11у 1),(х2,у2),---,(хт,ут)), где х, - ППС для объекта и„ а у, - ППСдля объекта /(w,) е W, 1< i < т.Рациональное число q кодируется ППС (х, у), где х и у ППС для целых чисел а и b , таких, что a/b = q и наибольшийобщий делитель а и Ь равен 1.Приведенный выше список кодов объектов довольнохорошо иллюстрирует понятие разумного кодирования.

Егодостаточно в большинстве встречающихся случаев. Дляописания условий задач можно ограничиться толькоперечисленными объектами, потому что другие типы объектоввсегда могут быть выражены через объекты, перечисленныевыше. Мы ограничимся только разумными схемамикодированияГЛАВА 2. ДЕТЕРМИНИРОВАННЫЕ МАШИНЫТЬЮРИНГА И КЛАСС РПОЛИНОМИАЛЬНЫХ ЗАДАЧДля формализации понятия «алгоритм», необходимозафиксировать модель процесса вычисления. Такой модельюбудет служить детерминированная одноленточная машинаТьюринга (сокращенно ДМТ), которая схематическиизображена на рис.2 Л ниже. Машина Тьюринга состоит изРяс. 2.1.