Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 80
Текст из файла (страница 80)
На самом деле возможен даже алгоритм с оценкой О(!)7!) (см задачу 5) Таким образом, задача ПЛАНАРНАЯ КЛИКА действительно является полиномиальным частным случаем задачи КЛИКА. С) Пример 16.3. Вспомним задачу МНОГОПРОЦЕССОРНОЕ РАС. ПИСАНИЕ, которая, как было показано в теореме !5.5, ЛгР-полна.
В этой задаче даны ориентированный ациклический граф (Я, А), описывающий ограничения предшествования для заданий, число з) В совезскай литературе ату теорему принято называть теоремой Поитрягииа — Куратовского См. примечание иа с. 4!7.— Прим ларса.
!б.б, Частные случаи и обобщения )ч'Р-полных ообоч 405 процессоров т и длина расписания Т, и спрашивается, существует ли допустимое расписание. Однако следующие частные случаи этой задачи полиномиальны 1. Т=2. Если в расписании должны использоваться только 2 единицы времени, то орграф (7, А) не должен содержать путей длины 2 или более; другими словами, это должен быть двудольный орграф с дугами, идущими из множества источников 3 в множество стоков Й, и, возможно, множеством! изолированных вершин.
В этом случае легко понять, что допустимое расписание существует тогда и только тогда, когда а) (Р1, (3(( гп и б) (Р(+ 1З(+ !)! ~ 2т. 2. т=2. В задаче 5 из гл 10 было показано, что задачу составления расписания для двух машин можно решичь за время О(п'). 3. (",г, А) — ордерево Другими словами, степень захода (/)(1 для всех l Е'зч, Для этого случая также имеется полиномиальный алгоритм (см задачу 6 и 1Нц(). Таким образом, некоторые интересные частные случаи задачи МНОГОПРОЦЕССОРНОЕ РАСПИСАНИЕ можно решить эффективно, несмозря ыа то что общая задача ХР-поляа.
() Еще один пример дает задача ВЫПОЛНИМОСТЬ: если число литералов в каждом дизъюнкзе ограничено двумя, то соответствующая задача (называемая 2-ВЫПОЛНИМОСТЬ) может быть решена за линейное время (см. задачу 6 нз гл 15). Другие примеры таких ситуаций можно найти в задачах в конце эзой главы 16.3.3. Трудные частные случаи А(Р-полных задач. Подход, рассмотренный в предыдущем подразделе, не всегда работает. Некоторые АГР-полные задачи остаются УР-полными, даже тогда, когда соответствующие им индивидуальные задачи существенно ограничены Очень часто наиболее интересные вопросы, касающие. ся АгР-полноты, включаю~ в себя точное понимание того, в каких частных случаях рассматриваемой НР-полной задачи содержится сложность этой задачи.
Доказательство того, что некоторый частный случай Л'Р-полной задачи сам является НР-полным, обычно включает в себя преобразование специального вида. Цель такого преобразования — модифицировачь произвольную данную индивидуальную задачу для общей задачи так, чтобы избавиться от особенностей, недопустимых в рассматриваемом частном случае, и не изменить очвета да или нееп в этой индивидуальной задаче. Мы уже встречались с таким преобразованием при доказательстве УР- полноты задачи 3-ВЫПОЛНИМОСТЬ (теорема 15.2), когда наша цель состояла в том, чтобы заменить днзъюнкты с числом литералов, отличным от трех, эквиваленчными множествами дизъюнктов с 3 литералами.
Приведем другой пример такого доказательства. Теорема 16.5. Задача ВЫПОЛНИМОСТЬ остается НР-полной даже для формул, в которых каждая переменная появляется один или два раза без отрицания и один раз с огприцанием. С Гл. !б, Еи!е еб ХР-полно!пе Доказательство. Рассмотрим лроизвояьную формулу Р и произвольную переменную х, встречающуюся в Р. Пусть в целом в Р переменная х входит й ) 3 раз. Вместо первого вхождения переменной х можно подставить новую переменную х„вместо второго вхождения — переменную х, и т.
д, вплоть до я-го вхождения. Теперь надо обеспечить, чтобы в любом наборе значений истинности, выполняющем формулу, значения истинности всех й переменных х„..., хх были одинаковы. Этого можно добиться, добавляя к формуле дизъюнкты (х,+х,) (х,-, 'х,)... (х,+л,); читатель может легко проверить, что эти новые дизъюнкты выполняются только тогда, когда все переменные х,,..., хх принимают одно и то же значение истинности. Если мы проделаем это преобразование для всех переменных, появляющихся в формуле более трех раз, то получим новую формулу, в которой все переменные встречаются не более трех раз, и эта формула будет выполнима тогда и только тогда, когда выполнима формула Р.
Выделим теперь все переменные, которые входяч в формулу либо только без отрицания, либо только с отрицанием. Очевидно, при любых попытках выполнить Р' мы можем выпочнить все дизъюнкты, в которых эти переменные встречаются, придав им соответственно значения истина или ложь, лри этом не возникнет никаких противоречий. Поэтому все эти дизъюнкты можно удалить из Р', и полученная формула опять будет выполнимой тогда и только тогда, когда выполнима формула Р.
Если в новой формуле некоторая переменная х встречается дважды с отрицанием и один раз без отрицания — это единственный оставшийся случай, когда нарушаются ограничения теоремы,— мы лодсзавляем в формулу у вместо х, где у — новая переменная. Легко проверить, что в получаемой формуле каждая переменная встречается один или два раза без отрицания н один раз с отрицанием. Г( Иногда для доказательства МР-полноты некоторого частного случая Л'Р-полной задачи достаточно заметить, что все индивидуальные задачи, которые строятся при доказательстве ИР-полвочы общей задачи, лежат внутри интересующего нас частного случая. Теорема 16.6.
Задача ГАМИЛЬТОНОВ ЦИКЛ г!Р-полна далее тогда, когда рассматриваются только те графы, в которых степени вершин не превосходят четырех. Доказательство. Достаточно заметить, что в графе, который строится в доказательстве теоремы 15.6, степени вершин не превосходяз 4. Е) Приведем в заключение более сильный результат. Теорема !6Л. Задача ГАМИЛЬТОНОВ ЦИКЛ для графов, в копюрых степени всех вершин равны 3, й(Р-полна. 1б,б. Частные олуипи и обобщеноя б<Р-полно<х эадп< 407 (а) (б) (в) (г) Рис. 16.3. Доказагпелбство.
Рассмотрим граф 6 (У, Е), в котором степени всех вершин не превосходят 4. Покажем, как избавиться от вершин степени 4 и 2. Начнем с вершин степени 4. Заменим в б каждую вершину о степени 4 подграфом, вершины которого имеют степень 3 или 2, изображенным на рис. )6,3(б). Тогда если этот подграф является частью произвольного графа, то гамильтонов цикл может проходить по нему только так, как показано на риг.
!6.3(в — д) (или еще тремя, полностью симметричными способами). Поэтому при любом таком преобразовании сохраняется су- Гл. ! б. Еще об ?? Р.полно»и 408 щестВОВание или песущестВОВание гамичьтонова цикла. Для ЗВВершения доказательства заметим, что можно избавиться от вершин степени 2, заменяя их так, как показано на рис.
!6.4. Рис. 16.4. 16.4 Словарь родственных понятий В этом параграфе мы рассмотрим некоторые вопросы, относящиеся к теории УР-полноты, и объясним их связь с понятиями, введенными и рассмотренными в предыдущих параграфах. !6.4.!. Полиномиальные сведения. В й 15 4 мы определили полиномиальное сведение задачи А к задаче В как полиномиальный алгоритм, решающий задачу А и «вызывающий» при этом несколько раз подпрограмму, решающую задачу В с единичной стоимостью. Однако мы сконцентрировали внимание на частном случае, а именно на полиномиальном преобриэооинии. Этого «более гочного» вариан ~а нам оказалось достаточно дтя развития теории Л'Р.полногы.
По~еряли ли мы что-нибудь, ограничив наше внимание полиномиальными преобразованиями? Никто не знаег, действительно ли класа й?Р-полных задач увеличится, если ослабить определение М Р- полноты, допустив более общие сведения — даже в том случае, если РФ НР. 16.4.2. МР-трудные задачи. Иногда удается показать, что все задачи из?1Р полиномиально сводятся к некоторой задаче А, но не удается доказать„что А Е?е'Р. Тогда А не может называться ФР- полной. Однако А, несомненно, настолько же трудна, как любая задача из дгР и поэтому, вероятнее всего, труднорешаема.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
