Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 71
Текст из файла (страница 71)
Чтобы понять это, достаточно заметить, что в худшем случае А, будет состоять из непрерывных вызовов А„каждый раз для наибольшего возможного входа. Возможно самое большее р,(п) таких вызовов; по какова может быть длина их входа? Даже если допустить, что алгоритм тратит все его р, (и) шагов только на выписываиие входов для А„то эти входы не могут быть длиннее, чем р, (я). (Здесь считается, что алгоритм может обрабатывать только один символ в каждый момент времени; рассуждения будут идентичны, если допустить одновременную обработку не более й)! символов или даже полиномиального — относительно длины входа— числа символов.) Следовательно, существует полиномиальный алгоритм для А П Мы увидим, что особый интерес представляет специальный внд полиномиальиого сведения, ИЯ теорема Кука Определение 15.3.
Будем говорить, что задача распознавания А, полинсмиальнс преобразуется в другую задачу распознавания А „ если по произвольной данной строке х можно за полиномиальное (относительно (х!) время построить такую строку у, что х является индивидуальной задачей задачи А, с ответом да тогда и толькотогда, когда у является индивидуальной задачей задачи А, с ответом ,~р „„„„, 7ч'Р да. (".) ээкачи Полиномиальные преобразования можно рассматривать как полиномиальные сведения всего лишь с одним вызовом подпрограммы для А, в конце алгоритма для Аь Остальная часть алгоритма просто строит у — вход со.
ответствующего алгоритма для А,. Примерами полиномиального преобразования могут служить преобразование задачи ВЫПОЛНИМОСТЬ в задачу ЦЛП (пример 13.4) и преобразование общей задачи о потоке мини- Рис. 15.2. Р и НР мальной стоимости в задачу Хичкока. (См.
3 7.5; легко проверить, что описанное преобразование применимо также к вариантам распознавания обеи х задач.) Определение 15.4. Задача распознавания А ЕФР называется !ч'Р-полной, если все остальные задачи из )УР полиномиально преобразуются в А. () Согласно предложению !5.1, если задача А является )ч'Р-полной, то она обладает сильным свойством: если существует эффективный алгоритм для А, то существует эффективный алгоритм для каждой задачи из (ч'Р. Сюда включаются такие старые и крепкие орешки, как ЗК, ЦЛП, ВЫПОЛНИМОСТЬ и КЛИКА. Понятие А(Р-полных задач и наше подозрение, что РФ)УР, приводят к изображению класса й)Р, представленному на рис.
!5.2; сложность на этом рисунке предполагается возрастаю1цей вверх. Конечно, пока совсем не очевидно, что существуют УР-полные задачи. Однако они действительно существуют, что будет показано в следующем параграфе. 1з.з Теорема Кука Чтобы доказать, что некоторая задача ЖР-полна, необходимо показать а) что задача входит в !УР; б) что все другие задачи из !УР полиномиально преобразуются в нашу задачу. На практике для доказательства и. (б) обычно показывают, что некоторую известную УР-полную задачу можно полиномиально преобразовать в рассматриваемую задачу. Так как свойство по- Зо4 Гл. 1д. НР.полные эадани линомнальной преобразуемости транзитионо — т.
е. если А полпномиально преобразуется в В и В полиномиально преобразуется в С, то А полиномиально преобразуется в С,— этого будет достаточно. Однако первое доказательство МР-полноты должно включать явное доказательство и. (б).
Для этого в доказательстве нужно использовать общие характеристики всевозможных задач из А)Р. Такими характеристиками, естественно, являются существование по Рис. !5,3. Алгоритм проверки удостовереиия. крайней мере одного удостоверения с(х) для каждой индивидуальной задачи х с ответом да и существование алгоритма проверки удостоверения А. Таким образом, нужно формализовать наше понятие алгоритма проверки удостоверения. Этот алгоритм можно представлять себе как )сгройство, которое читает и преобразует символы некозорой строки, по одному символу за единицу времени, с помощью читающей и пишущей головки; ее работа, движения и другие решения упправляю1си программой (рис. !5.3). В исходном состоянии головка обозревает самьш левый символ строки и программа начинает выполнять свою первую команду.
Команды программы имеют вид 1: !! и 1Ьеп (о'; о; 1'), где 1 и 1' — номера команд (меткн), о и о' — символы алфавита л, и о — одно из чисел, 1, 0 или — 1. Выписанная выгпе команда имеет следующий смысл. Если в данный момент обозревается символ о, то стереть его и написать на его месте о', сдвинуться на о позиций вправо и далее выполнять команду с меткой 1'; в противном случае выполнять следующую команду, Сдвиг на 0 илн — ! разрядов вправо означает соответственно, что головка остается в той же позиции или сдвигается на 1 влево. Последняя команда программы имеет вид ! е(: яссер1, где ~А! — длина программы, т.
е, общее число команд в ней. Будем говорить, что строка х9с(х) приншнается алгоритмом »о.о, Теорема Кука ,й, если этот алгоритм, начиная в правильном положении обрабатывать данную строку, после не «юлее р()х() шагов приходпг к последней команде, где р(п) — полиномиальная граница для А. Если алгоритм выполняет р()х!) команд и не достигает команды ассерГ (прпнять) или если ~оловка сходит со с1роки, то будем говори«ь, что хйс(х) отвергается. Таким образом, класс МР можно более формально определить как множество задач распознавания, для которых существуют алгоритм проверки удостоверения А и полинам р(п), такие, что х является индивидуальной задачей с ответом да тогда и только тогда, когда существует такая строка с(х), что ~с(х))(р(~х~) и Л принимает х9с(х). Эта модель алгоритма проверки удостоверения может на первый взгляд показаться несколько примитивной и ограниченной по своей силе. Рассмотрим несколько возможных претензий.
Е Создается впечатление, что работа алгоритма ограничена пространством, занимаемым строкой, и больше нет «чистой бумаги». Тем не менее это возражение легко отвести, заметив, что удостоверение можно определить так, чтобы оно содержало в себе достагочное количество дополнительного орос«ранг~аз например, длинную с1року «пробело⻠— для и) жд алгоригма. 1ак как злгори1м полпномиален, он не может потребоиа~ь более чем полино.
мяального количества такого пространства, и поэтому длина удостоверения остается полиномиальной. Учитывая это, мы всюду в дальнейшем будем принимать упрощающее допущение, что для всех х одного и того же размера длина с(х) равна ~с(х)~=-р(~х!) — ~х~ — Е Следовательно, длина всего входа х9с(х) в точности равна р(~х!). При этом не происходит потери общности, поскольку, если удостоверение короче, его всегда можно дополнить несколькими пробелами до указанной длины. С другой стороны, входы, длина которых превышает р(~х~), несущественны для Е, так как о«не может даже просмотреть полностью такой вход за р(~х!) шагов. 2.
Другая возможная претензия к силе нашей модели вычисления состоит в том, что набор допустимых «команд» очень ограничен. Однако должно быть ясно, что нашу ограниченную модель можно использовать для моделирования более сложных команд (например: Делать следующее до гпех пор, пока обозреваемый символ не совпадет с $, Сдвинуться на 7 позиций вправо, Удалить текущий символ)„добавляя при этом в общее число шагов всего лишь мультипликативную постоянную. 3.
Наиболее существенным отступлением от этой модели было бы разрешение адресации; т. е. таких команд, как Сдвинуться на пягпнадцатый символ строки (или даже Сдвинуться вправо на числа позиций, равное двоичному целому числу, заключенному между текущим символом и первым символом $ вправо от него), что напоминало бы обычные вычислительные машины с произвольным доступом к памя«и. Однако читатель может проверить, что общее числ Гл. !д. Гч'Р-полные задачи шагов при нашем ограничении может умножиться приблизительно на р()х!), так как любой позиции в строке можно достичь за это время. Таким образом, нам хотелось бы утверждать, что наша модель алгоритмов проверки удостоверения — это достаточно реалистичная и общая модель, в которой можно выразить эффективные алгоритмы для любой задачи, для которой вообще возможны эффективные алгоритмы.
Так как эта модель является, по существу, машиной Тьюринга, то дальнейшее обоснование нашего утверждения можно получить, рассматривая элегантные рассуждения А. М. Тьюринга (Тц), Дополнительные технические обсуждения см. в гл. 1 книги (АН1Л. Воспользуемся описанным формальным определением для доказательства следующего важного результата, принадлежащего Куку. Теорема 15.1. Задача ВЫПОЛНИМОСТЬ )ч Р-полна.
ДоказательстволВ примере 15.7 было показано, что задача ВЫПОЛНИМОСТЬ содержится в !ч' Р, Поэтому остается показать, что если А — некоторая задача из ИР, то А полиномиально преобразуется в ВЫПОЛНИМОСТЬ. Другими словами, для данной строки х мы должны построить формулу Р(х) — используя только тот факт, что А ЕИР,— такую, что х является индивидуальной задачей задачи А с ответом да тогда и только тогда, когда формула Р(х) выполнима. Для этого рассмотрим алгоритм А проверки удостоверения для А, время и память которого по нашему предположению атом, что А Е ИР, ограничены некоторым полиномом р(п).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
