Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 78
Текст из файла (страница 78)
Спрашивается, существует ли такой рациональный пвектор х, что Ах Ь. 397 1ь,д Класс со-??Р Как выглядит дополнение задачи ЛН? Теория двойственности утверждает, что неравенства Ах<Ь недопустимы тогда и только тогда, когда двойственная задача пип р'Ь, рл=о, (16.1) др:о неограниченна (она допустима, так как д=о — решение).
Мы применили здесь двойственную конструкцию к задаче пчахо х, Ах <Ь, х~~о Однако задача (16.1) неограниченна тогда и только тогда, когда она имеет решение с произвольной отрицательной стоимостью. По- Рнс. 16.1. Уточненная предполагаемая картина класса ИР. этому вариант нет-да индивидуальной задачи ЛН Ах<Ь сам является индивидуальной задачей ЛН, а именно задачей с неравенствами дл<о, длеко, д-.о, р Ь< — 1. Получаем, что задача ЛН является своим собственным дополнением и принадлежит, таким образом, обоим классам Ь?Р и со-ЖР.
Естественно, этот результат не производит большого впечатления, так как мы знаем, что задача ЛН принадлежит Р (см. гл. 8). Однако в годы неопределенности, предшествовавшие появлению алгоритма эллипсоидов, этот факт — ввиду теоремы 16,2 — был Гл. 1В. Е«ге ов ггя-пол«юнге единственным теоретическилг свидетельством в пользу того, что задача ЛП не является труднорешаемой. Наши выводы и гипотезы. связанные с классом со-ИР, позволяют построить более детальную диаграмму для ЖР, чем диаграмма, приведенная на рис.
15.2 (см. рис. 16.1). и.г Псевдополииомиальчые алгоритмы и «сильиаяя АгР-полнота Напомним задачу ЦЕЛОЧИСЛЕННЫЙ РЮКЗАК, которая, как было доказано в гл. 15, ФР-полна. Пусть с„..., с„, К вЂ” соответствующая индивидуальная задача; спрашивается, естественно, гз Рис, !6.2. СУЩЕСтаУЮг ЛИ таКИЕ ЦЕЛЫЕ ЧИСЛа Х„Х.„..., Х„)0, Чта ~г"„ге!к!= =К. Для произвольной индивидуальной задачи можно построить следугощий орграф О(с„..., сп; К)=-()г, А): )г=',О, 1, 2, ..., К), А=((т, к): О~а < кк 'К и 1г — лг=с для некоторого 1(н). Таким образом, граф О(с„, с„; К) имеет К+1 вершин и О(нК) дуг. В качестве примера на рис.
162 приведен граф О(3, 7; 13). Лемма 16.1. В графе О(с„..., с„; К) ижеетсл путь из 0 в К пгогда и только тоеди, когда индивидуальнал задача ЦЕЛОЧИСЛЕННЫЙ РЮКЗЛК (с„..., с„; К! имеега решение. Докизительсогво. Пусть (О = — гтп г',, ..., г« == — — К) — путь в О. Рассмотрим последовательность (6„..., 6 )=(1г — г',, ..., г — г,). Все числа 6,, ..., 6 содержатся среди (с„..., с„) согласно определению орграфа О. Кроме того, ~, гбг = К.
Отсюда следует, что уравнение имеет неотрицательное целочисленное решение,.а именно решение, в котором хг берется равным числну появлений с, в последовательности (6„, 6„). Обратно, если ~г",с>хг=К для неотрицательных гелых чисел х„..., х„, то можно восстановить некоторый путь из 0 399 Г6,2. Лгеадонолггномнальные алгоритма в К в орграфе 6(с„..., со; К), положив з, рзз зз рзз рзз Тогда путь из () в К будет иметь впд !() === го, ..., г = К), где 1,=- ~г;- бг С3 Это приводит к слсггующему рс улыагу.
Теорема 16.3. Любую индивидуальную задачу ЦЕЛОЧИСЛЕННй)И Р)ОКЗЛК (с„..., сн, К) лгоочно реиатьзивуемяО(пК). Догоозоигелгсгггвгн По данным (с„..., сь, К) 'можно за время 0(аК) пострщпь г рграф 0(с„..., с„; К). Затем за время 0(оК) определим, суи;естпует лн путь из 0 в К, используя алгоритм НАЙТИПУТ1> из гл. 9. Согласно приведенной выше лемме, этим решается исходная индивидуальная задача ЦЕЛОЧИСЛЕННЫЙ РЮКЗАК, П Теорема 16.3 вьнляднт как ксключителню важный результа~. Известную йгР-полнуго задачу — ЦЕЛОЧИСЛЕННЫЙ РЮКЗАК— можно решить с помощью алгоричма, временная оценка которого выражается вполне полнномиальной функцией! Значит, мы доказали, что Р=МР».
На самом деле, конечно, оК не нолиномиальная функция относительно длины входи. Лля записи кода индивидуальной задачи ЦЕЛОЧИСЛЕННЫЙ РЮКЗАК требуется около и !ои К ячеек пам»пи, ~ак как целые числа в агом случае можно записать в двоичной или десятичной системе счисления Поэтому 0(пК) не является полиномиальной оценкой. Тем не менее теорема 1б.З остается очень любопьппым фактом. Она показывает, что наше разбиение алгоритмов на пракчические и непрактическне (в зависимости от того, выпольимы ли они за полииомиальное время относи~ельно длины входа) условно.
При определенных обстоятельствах алгоритм с оценкой 0(ггК) ыоже~ рассматриваться как практический, несмотря на его экспоненциальное поведение. Пусть, например, в некотором приложении задачи ЦГЛОЧИСЛ1-:ННЫЙ РЮКЗАК мы стараемся максимизировагь выгоду нли деньги, получаелгые предприятием. Тогда временная оценка 0(оК) показывает, чго для достижения этого максимума мы должны загратить фиксированный -- н, пало надеяться, очень малый — пропент доходов для оплаты машинного времени. А эго может рассматриваться как разумная и практически допустимая политика.
Кроме того, в следующей главе мы увидим, что «псевдополиггомиальные» алгоритмы, такие, как описанный выше алгоритм с оценкой 0('оК), могуг указьгвагь на дальнейгцие положительные алгоритмические свойства рассматриваемой задачи, несмотря на то что она АгР-полна. Таким образом, оказывается, что некоторые экспоненциальные алгоритмы не так уж катастрофичны. Гл. /о. Егце оо /г'Р-но»ноям Приведенные выше рассуждения показывают, что длина кода не является единственной разумной мерой «размера» индивидуальной задачи.
Рассмотренный пример задачи ЦЕЛОЧИСЛЕННЫЙ РЮКЗАК приводит к следующему определению. Определение 16.2. Пусть ! — индивидуальная вычислительная задача — обычно / будет последовательностью комбинаторных объектов, таких, как графы, множества или целые числа.
Тогда пцш(/) — это наибольшие целое число, появляющееся в /. Например, для индивидуальной задачи ЦЕЛОЧИСЛЕННЫЙ РЮКЗАК != (с„..., с„, К) эта величина будет равна пцш(/)=К (при разумном предположении, что с,,..., с„К). Если /=(/!, /т) — индивидуальная задача КЛИКА, то пцш(/)=-/т'). Пусть /= =- (а, (йг/), !.) — индивидуальная ЗК. Тогда пцш (!) — это наибольшее целое число среди (л, )йг/), г — 1,, и, !=1,...,л, ! ).
Приведенное определение сразу же указывае~ на один очень важный аспек~. В некоторых задачах, таких, как КЛИКА, функция пцш для индивидуальных задач имеет естественную границу; так, для задачи КЛИКА в индивидуальной задаче 6=((У, Е), /г) не имеет смысла брать /т))У). В других трудных задачах, таких, как ЗК, нет естественных границ на размер целых чисел, появляющихся в соответствующих индивидуальных задачах. Однако эти неограниченные целые числа не влияют на сложность данной задачи: при доказательстве й/Р-полноты ЗК наибольшее целое число, которое нам пршцлось построить, было равно п (вспомните доказательство следствия 2 из теоремы 15.6). С другой стороны, имеются задачи, такие, как ЦЕЛОЧИСЛЕННЫЙ РЮКЗАК, которые обязаны своей сложностью именно неограниченному размеру целых чисел, появляющихся в соответствующих индивидуальных задачах.
Так, при установлении А/Р-полноты задачи ЦЕЛОЧИСЛЕННЫЙ РЮКЗАК нам пришлось прибегнуть к построению громадных целых чисел. Похоже, что это необходимо, особенно ввиду теоремы 16.3. Все это приводит к следующему определению, Определение 16.3. Пусть А — вычислительная задача и !— функция, отображающая Аг в Аг. Через А, будем обозначать задачу А, ограниченную на индивидуальные задачи !, для которых пцп) (/) ( !((/)), где )/) — длина кода, представляющего индивидуальную задачу / Будем говорить, что задача А сильно А«Р-полна, если для некоторого полинома р(п) задача Ая гт'Р-полна.
Пример 16.1. Задача КЛИКА сильно А«Р-полна, так как задача КЛИКА„совпадает с задачей КЛИКА. Напомним, что /г=пцгп (/) а и=' )У) для любой разумной индивидуальной задачи КЛИКА /.= ((1', Е), к). Аналогично, ЗК сильно А/Р-полна, поскольку, как показывает доказательство следствия 2 из теоремы 15.6, она оста- ') Если /= ((У, Е), я) — индивидуальная задача КЛИКА, то можно возразить, что ошн (/)=1У), так как для представления вершин графа (У, Е) неисходимо использовать индексы вплоть до)У(.
Однако этот момент не играет существен. ной роли в наших рассуждениях. 401 16.2, Лаедополнномивльные алгоритмы ется ЖР-полной даже в том случае, если участвующие в ней целые числа ограничить числом городов. Также сильно ИР-полными являются задачи ГАМИЛЬТОНОВ ЦИКЛ, 3-МЕРНОЕ СОЧЕТАНИЕ, МНОГОПРОЦЕССОРГ!ОЕ РАСПИСАНИЕ, ТОЧНОЕ ПОКРЫТИЕ 3-МНОЖЕСТВАМИ, а также все другие ФР-полные задачи, (УР- полнота которых может быть установлена с помощью преобразований, не использующих экспонеициально больших целых чисел.
Напротив, задачи 0-)-РЮКЗАК, РАЗБИЕНИЕ и ЦЕЛОЧИСЛЕННЫЙВ РЮКЗАК не попадают в этот класс. Определение !6.4. Алгоритм и( для задачи А называется псевдонолиномиальным, если он решает любую индивидуальную задачу 1 задачи А за время, ограниченное полиномом от (1! и пцш(У). Г) Таким образом, алгоритм со сложностью 0(пК), который реша. ет задачу ЦЕЛОЧИСЛЕННЫЙ РЮКЗАК, является, очевидно, псевдополиномиальным алгоритмом.
Как уже отмечалось, наличие для задачи псевдополиномиального алгоритма — во многих отношениях положительный факт. В следующей теореме устанавливаезся, что сильная НР-полнота делает маловероятным существование псевдополиномиального алгоритма точно гак же, как УР- полнота делает маловероятным существование полиномиальных алгоритмов. Теорема 16.4.
Если Р Ф (У Р, то ни для кикой сильно (У Р-полной задачи не может сди4ествовать псевдополиномиольного илгоритма. Доказательство. Пусть А — сильно МР-полная задача; другими словами, для иекозорого полинома р(п) задача А,„, А'Р- полна. Кроме того, пусть для А существует псевдополиномиальный алгоритм 4, который решает любую индивидуальную задачу ! задачи А за время д(!(!, пцш(!)) для некоторого полинома д от двух переменных. Тогда очевидно, что 4 решает МР-полную задачу Арин за время д(п, р(п)), являющееся полиномом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
