Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 77
Текст из файла (страница 77)
М. Ребиг!Ы1!!у ашопй СошЫпа1опа| РгоЫешэ, рр. 85 — 103 |п Согпр|ехйу о! Согпршег Согпрп1аИопэ, ед )1. Е. М|1|ег апб 3. Ъ' Тйа|сЬег. Хек Уог)г. Р)епиш Ргеш, 1972. (Имеется перевод: Карп Р. М. Сводимгмть комбинаторных проблем.— В сбл Кибернетический сборник, новая серия, вып. 12.— Мл Мнр, 1975, с. 16 — 38,1 Среди многих других результатов, связанных с Л(Р-полнотой, в этой работе можно найти оригинальные доказательства чеорем |5.3, 15.4. 15.6, 15.7 и 15 8 и решения задач 10, 12 и 13 Превосходным руководством по Лгр-гюлпоте может служить статья !Ка2) Кагр й.
М. Оп |ЬеСошр!ех||у о1СошЫпа1ог!а! Р~оЫегпз, Ке1ъогйэ, 5 (1975), 45 — 68. Энциклопедией по этому попросу является замечательная пиита Гэри н Джонсона; [О3) Оагеу М. й., 3ойпзоп О. 5. Сотрь|егэ апб 1п(гас.аЫ1йу: А Сш!бе |о |Ье ТЬеогу о1 Л(Р-сотр1е(еггезз Зап Ргапс|зсо. %'. И, Ргеегпап л Согпрапу, РнЫ)эцегз, 1979, [Имеется перевод: Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.— М.. Мир, 1982.! Эта книга дает воэможность оценить богатство и разнообразие класса МР.полных задач. Теорема 15.5 была впервые доказана в статье [В![ 1)1|гпап 3 О.
Л(Р-сотр!е(е Зсцебцйпй РгоЫешз, 3СЗЗ, 1О (!975), 384 — 393. Наше доказательство следует работе [ЬВ) Ьепз(га 3. К., 9)попу Кап А. Н. О. Сошр1ехцу о1 Зсйебц||пй нпбег Ргесебепсе сопшга|п1з, ОТО 26 (1978), 22 — 35. Следствие 2 из теоремы 15,8 взято нз работы [Ьн[1 цейег О. 5. Тво МР-сотр1е(е РгоЫешз !п МоппейаИче1п1ейег Ргойгашш!пд, Тр 178, Ргтге1оп Оп(чегз(!у, |975.
Задача 11(е] принадлежит Гэри и Джонсону. Задача 14 взята из [Ра1[ Рараейгпйпоц С. Н. Оп |Ье Сошр|ехИу о1 Едде Тгачегэ|пй, 3. АСМ 23 (1976), 544 †5 Решение задачи 15, принадлежащей Кнуту, приведено в [Ка2[. Задача!7 взята иэ Кожиенаарии и шылки 393 [Ра2) Рарабппйшон С. Н. Тйе Енс!Ыеап ТЗР (з НР-сошр'е!е, Т)геог. Сошр Зс!., 4 ()977), 237 — 244. Задача !8(б) взята из (0ВЦ. Уверенность читателя в обшнсоги нашей модели алгоритмов проверки удостоверения может возрасти после рассмотрения .адач 7 — 9. Наша модель — это вариант машины Тьюринга; см.
'гТп) Тншпй А. М. Оп Сопзрп(аЫе НпшЬегз зчг(й ап Арр)(са((оп (о гйе Еп(зсйе(- бнпйзргоЫып, Ргос. Еопбоп Майк Бос. Бег, 2, 47 (!936), 730 — 766. Эквивалентность этой и других моделей обсуждается в книге (АН()! Айо А. Ч., НорсгоН 3. Е., ()()шап ). 0 Тне Оез)йп апб Апа)уз)з о! Сош. ршег А)йог((йшз, Сйар(ех !. )(еаб(пй, Мази Абб(зоп-Ве.)еу РпЫ)зЫпй Со, )пс., !974. (Имеется перевод: Ахо А., Хопкробп Лж., Ульмак Лж. Пгюгрое. нне и анализ вычислительных алгоритмов.— Мс Мир, !979.! !6 Еще об КР-полноте В этой главе мы продолжим обсуждение )УР-полных задач, обращаясь к некоторым важным аспектам, окружающим понятие ФР-полнотьь 16.1 Класс со-)чР Вспомним следующую известную нам задачу типа да-нет: ГАМИЛЬТОНОВ ЦИКЛ Дан граф 6=(г', Е).
Спрашивается, является ли граф 6 гамильтоновым, т. е. имеется ли в 6 гамильтонов цикл. Легко показать, что эта задача входит в НР, поскольку каждая ее индивидуальная задача с ответом да имеет короткое удостоверение — а именно сам цикл. Рассмотрим, однако, следующий вариант типа непг-да той же задачи; ДОПОЛНЕНИЕ ГАМИЛЬТОНОВА ЦИКЛА Дан граф 6=((', Е). Выяснить, является ли граф 6 негамильтоновым.
Совсем не очевидно, что эта задача принадлежит НР. На самом деле мы скоро увидим, что, вероятнее всего, она не принадлежит МР) Единственный известный на сегодняшний день общий метод для доказательства того, что некоторый граф не является гамильтоиовым, состоит в систематическом выписывании всех циклов графа 6 и проверке того, что ни один из них не содержит всех вершин.
Конечно, этот список является удостоверением, но, к сожалению, он имеет экспоненциальную длину. В общем случае задача А является дополнением задачи А, если множество строк, составленных из символов алфавита х, кодирующих индивидуальные задачи А с ответом да, в точности совпадает с множеством строк, не являющихся кодами индивидуальных задач А с ответом да. Таким образом, строго говоря, задача ДОПОЛНЕНИЕ ГАМИЛЪТОНОВА ЦИКЛА ие является дополнением задачи ГАМИЛЬТОНОВ ЦИКЛ, так как существуют 395 !бд. Класс со.КР строки, не являющиеся кодами индивидуальных задач с ответом да ни для А, ни для А: это строки, ко~орые вообще не кодируют ни.
какого графа, гамильтонова или не гамнльтонова. Однако эти ос тальные индивидуальные задачи не влияют на сложность всей задачи, так как их всегда можно распознать с помощью простой «синтаксической проверки» н быстро избавиться от них. Поэтому на практике допустимо игнорировать этот момент и рассматривать указанные выше две задачи как дополнения друг друга. Другой пример дает следующая задача, являющаяся дополнением ЗК: ДОПОЛНЕНИЕ ЗК Даны целое число и, целочисленная (п ха)-матрица ~с(,,~ и целое число Е. Спрашивается, верно ли, что ~ч,", <д;, „, ) Е для всех циклических перестановок (обходов) т. Опять совсем не ясно, как для индивидуальной задачи ДОПОЛНЕНИЕ ЗК с ответом да построить удостоверение короче, чем представление всех обходов вместе с соответствующими стоимостями, которые все больше Е.
Рассмотрим, однако, следующее дополнение задачи, про которую известно, что она входит в Р: ДОПОЛНЕНИЕ СВЯЗНОСТИ Является Ли данный граф 6 несвяз><ым? Алгоритм ПОИСК, который решает задачу о связности за полиномиальное время, можно, очевидно, использовать для решения ее дополнения. Таким образом, задача ДОПОЛНЕНИЕ СВЯЗНОСТИ также входит в Р. Очень легко доказать общее утверждение на этот счет, Теорема 16.1. Если А — задача из Р, то дополнение А задачи А также входит в Р. Доказал<властев. Так как А принадлежит Р, то существует полнномиальный алгоритм, который решает А. Полнномиальный алгоритм для решения дополнения задачи А -- это в точности тот же алгоритм, только с заменой да на нет и наоборот.
Такие же рассуждения нельзя применить для доказательства того, что дополнение произвольной задачи из 1»' Р также принадлежит А<Р. Это связано с наличием определенной асимметрии в самом определении класса )ч' Р; если х — индивидуальная задача с ответом да для задачи А Е А<Р, то для нее имеется подтверждающее это удостоверение; однако, если это индивидуальная задача с ответом нет, о><а может не иметь короткого удостоверения для доказательства этого факта, На самом деле, как показывают наши примеры, в (ч' Р имеется по крайней мере две задачи, дополнения которых, вполне вероятно, могут не принадлежать »)Р.
Это приводит к следующему определению. Определение !6Л, Классов-НР— это класс всех задач, являющихся дополнениями задач из г7Р. Г) Таким образом, утверждение о том, что дополнения всех;адач из 7т'Р также принадлежат НР эквивалентно утверждению о том, что МР = со г7Р. Однако имеются причины подозревать, что ЖРФсо-МР. На этот счет имеются косвенные соображения, такие же, как насчет гипотезы РРРР: многие способные исследователи безуспешно потратили немало времени на построение коротких доказательств для свойства негамильтоновости, а также для многих других дополнений коротко подтверждаемых свойств. Тем не менее доказательства этой гипотезы пока нет, так же как и гипотезы о том, что РФА(Р. Однако можно показать (так же, как и для Р~=Д7Р), что если эта гипотеза верна, то о ее справедливости будут свидетельствовать МР-полные задачи.
Теорема !6.2. Если дополнение некоторой (УР-полной задочи принадлежит гчР, то МР =со-ИР. Доказательство. Предположим, что дополнение С некоторой АГР-полной задачи С принадлежит МР; покажем, что тогда дополнение А любой задачи А из МР также принадлежит г(Р. Так как задача С МР-полна, то А полиномиально преобразуется в нее; заметим, что это преобразование является также полино. миальным преобразованием задачи А в задачу С. Поэтому можно представить короткое удостоверение для любой индивидуальной задачи А с ответом да: оно состоит из а) списка операций указанного полиномиального преобразования, дающего в результате индиви. дуальную задачу С с ответом да, и б) удостоверения для этой индивидуальной задачи С вЂ” такое удостоверение существует, так как С принадлежит г7Р. Полное удостоверение полиномиально по длине, так как по предположению рассматриваемое преобразование полиномиально. Получаем, что А принадлежит (г'Р.
Так как в качестве А была взята произвольнаязадача из г(Р отсюда следует, что ЯР=со-ИР Таким образом, среди дополнений всех задач из уР дополнения Д(Р-полных задач с наименьшей вероятностью принадлежат й(Р. Обратно, если дополнение некоторой задачи из МР также принадлежит НР, то это свидетельство в пользу того, что задача не является МР-полной. Вспомним, например, следующую задачу распознавания, эквивалентную, как показано в 5 8.7, задаче линейного программирования; ЛИНЕЙНЫЕ НЕРАВЕНСТВА (ЛН) Даны целочисленная (тхп)-матрица А и целочисленный твектор Ь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
