Н.М. Новикова - Дискретные и непрерывные задачи оптимизации, страница 3

Временная сложность А' — Тд Я < Тд,( ) + Та(руЯ) — полипом. Аналогично доказывается (при замене слова ЛМТ на НЛМТ) УтВеРждение 5. Если П' ос П и П б ХР, то и П' б гчР. Опгкдклкник 7. Массовая задача П называется ХР-полкой ала уивеерсальиой, если П б ХР и 1гП' б ХР П' ос П (т.е. любая иедермииироваино полиномиальиая задача полкиомиальио сводится к П). Класс всех ХР-иолиых задач (распознавапия свойств) обозначается ХРС (ХР-сощр1есе). Непустоту класса ХРС доказал С.

А. Кук в 1971 г. Им была рассмотрена задача о выполпимости (ВЫП): выяснять выполнимость конъюпктивпой пормальпой формы (КНФ) — коиъюикпии конечною числа дизъюпктивпых функций, т.е. дизъюнкпий булевых переменных э; или их отрицаний э<. А именно, в задаче ВЫП требуется распозпать для КНФ па входе, существует ли выполпяюший набор яе (для которого значение КНФ равно 1). Ткогкмя 2 (8. А.

Соок). ВЫП б ХРС. Локязлткдьство полиномиальпой сводимости к ВЫП любой педетермипированпо полиномиальиой задачи осповаио на формальпой записи условия принадлежпости слова и языку из класса ХР (того, что и припимается иекоторой НЛМТ, а значит, и какой-то ЛМТ) в виде набора дизъюпктивиых фупкпий от специально вводимых булевых перемепных, связанных с состояниями ЛМТ в различные моменты времени, и является недостаточно простым для вводного курса (см. (1,2)). Поэтому мы лишь убедимся в том, что ВЫП б ХР. Лействительио, входное слово (параметры, определяющие индивидуальную задачу выполнимости) содержит число дизъюпктквных фуикпий в КНФ и указание для каждой из них, какие переменные входят с отрицапием, а какие пе входят вообще. Ллииу такого слова можно ограничить снизу суммой длии дизъюнктивпых фупкпив, помимая под длиной функции число ее переменных (или число знаков дизъюнкпии + 1).

Если теперь,в качестве подсказки для определяемов входным словом КНФ взять я~ — выполняющий ее набор, то вычисление на пем значения КНФ (проверка выполнимости) потребует такого же по порядку числа шагов. Иэ определсиия ХР-полпоты непосредственно следует Утвкгждкник б. Если РПХРС Рй, то Р= ХР.

А сели ХРС П(ХР 1Р) ф 9, то ХРС С ХР ~ Р. Таким образом, если бы удалось пайтк полиномиальиый алгоритм решения хоть одной ХР-полпой задачи, то были бы построеиы 13 полиномиальные алгоритмы решения всех ХР-полных задач и всех задач из класса ХР, а если для какой-либо ХР-полной задачи доказать отсутствие полнномиэльного алгоритма ее решения, то зто пе только дает строгое включение Р С ХР (т.е. ответ к основной проблеме теории сложности), но и влечет за собой доказательство невозможности построения полиномиального алгоритма решения любой задачи из класса ХРС.

Поскольку нп того, ни другого пока не сделано, считается, что зэлачи из ХРС отвечают житейскому представлению о трудной задаче и вряд ли допускают эффективное решение. Поэтому, если встречается задача, для которой на практике не удается придумать непереборный алгоритм, то имеет смысл попытаться доказать ее ХР-полноту, чтобы оправдать применение к ней тех нли иных переборных схем.

3. После того как была установлена непустота класса ХРС (теоремой Кука), появилась возможность доказательства ХР-полноты массовой задачи П путем полипомиального сведения к П одной из известных ХР-полных задач (соответствующий список см. в (1]). Лействительно, из утверждения 3 следует Тпогвмя 3 (крашерая ХР-воляошы). Массовая задача П распознавания свойств ХР-полна тогда и только тогда, когда она принадлежит классу ХР н к ней полиномиально сводится какая-либо ХР-полная задача: (П Е ХРС) Ф=~ (П Е ХР и ЗП Е ХРС: П' сс П). Пользуясь теоремой 3, можно показать ХР-полноту задачи о существовании целочисленного решения сястемы линейных неравенств с целыми коэффициентами (ЦЛН). Утверждение 7. ЦЛН Е ХРС.

Локязяткльство. 1) ЦЛН Е ХР, так как подсказкой может служить решение системы, а его проверка сводится к умноженшо на заданные коэффициенты и сложению, что не превосходит полинома от длины записи всех коэффициентов (доказательство полиномпальности длины записи решения см. в [2, с. 330]). 2) ВЫП сс ЦЛН. Общий вид системы линейных неравенств п11я1+вузяз+ ° ° ..+вуале < 61, Я = 1, ° ° °,пФ. Нетрудно представить в подобной форме условие истинности дизьюнктивной функции. Лля этого заменим в каждой у-й функцни знаки 14 дизъюнкции знаками суммы, а отрицания переменных ят — на (1-я;) н напишем для получившейся линейной функции условие > 1, добавив ограничения вт > 0 и вт ( 1 на все переменные. Пелочисленное решение яо = (зто) системы всех построенных неравенств является выполняющим набором для исходной КНФ (так как истинность КНФ эквивалеытыа истинности всех образующих ее дизъюнктивных функпин).

Таким способом решение любой индивидуальной задачи о выполнимосты сводится к решению некоторой индивидуальной задачи 1 б ЦЛН. Нолиномиальность сведения очевидна. Заметим, что фактячески в п.2 данного доказательства доказан более сипьный результат о сведении ВЫП к подзадаче ЦЛН вЂ” за даче о существовании булева решения системы линейных неравенств . с целыми коэффициентами (БЛН). Доказательство принадлежности БЛН классу недетерминнрованно полиномиальыых задач повторяет п.1 данного доказательства без ссылки на [2] (так как полыномиальность длины булеза решения очевидна), тем самым получено ы Утвкгждкыык 8.

БЛН б тчРС. $3. Классы слозкности. Сильная ХР-полнота и псевдополиномиальность Поквзатпельство гтР-полиоты задачи о у-еыполпимостпи. Взвимоотпкоитекие классов Р, ХР и т1РСт ХР и со-1ь1Р. ЯР-трудные задачи. Класс РНРАСЕ. Псеедопотииомиальпые в теоритмы. Пример для задачи о ртокзвке. Сштьиая ЫР-полпотпа. Теорема о связи сильной ртР-полиотпы звдачи с сртнествоввиием псевдополипомиальиого алгоритпма ее решения. 1. Кроме задачи о выполнимости, ХР-полнота всех остальных известных задач из класса ХРС (в том числе и КМ) была доказана ыа осыове теоремы 3 с помощью полнномиального сведения.

Общие рецепты доказательства полиномиальыой свсдимости (см. в [1]) легко использовать лишь в простейших случаях. Чтобы ыаучиться их применять, надо разобрать большое число примеров (в частности, имеющиеся в [1,2]), ыа что у нас в рамках данной работы нет возможности. Однако, еще один пример будет далее приведеы с пелью показать, что не только любая подзадача сводится к соответствующей задаче (автоматически), но возможно и обратное сведение. 15 Рассмотрим частный случай задачи о выполнимости, когда в КНФ могут входить лишь диэъюнктивные функции трех переменных (3-ВЫП).

Поскольку В(З-ВЫП)СВ(ВЫП), то по определению 3-ВЫПссВЫП. Так что 3-ВЫПйг1Р (по утверждению 5). Но ее ХР-полнота требует специального доказательства, ибо частные массовые задачи содержат меньше индивидуальных задач и могут оказаться проще; например, аналогичная задача 2-ВЫП полиномиальна. Пля получения результата 3-ВЫП б ХРС докажем, что 1З1Р- полная задача,о выполнимости сводится к своей подзадаче (частыому случаю) З-ВЫП.

Утвкгждкник 9. ВЫП о~ З-ВЫП. Покязяткльство. Покажем, что-произвольную дизъюнктивную функцию Р (як) й переменных можно представить в виде коыъюнкции дизъюнктивных функций от трех переменных (за счет введения дополнительных переменных и~). Обозначим через у< переменную я( или у~ в зависимости от того, как 1-я компонента як входит в рассматриваемую дизъюнктивную функцию; тогда последнюю можно записать как у1 Чуз Ч...Чуя и при Й > 3 заменить ыа КНФ: (у1 Ч уз Ч и~ )йс(уз Ч и~ Ч йз)йс(у~ Ч из Ч йз~рс... ...Й(уь з Ч иэь 4 Ч иээ э)йс(уь 1 Чуя Ч йь з). Отметим, что данная замена не является эквивалентной.

Пействительно, если исходная дизъюнктивная функция равнялась нулю, то построенная КНФ равна нулю при всех значениях и, но если исходная дизъюнктивная функция равнялась 1, то найдется такое значение и, чтобы КНФ равнялась 1. Этого, однако, достаточно для сохранения ответа на вопрос о сушесгвовании выполняющего набора. УПРАЖНЕНИЕ 4. Завершить доказательство ХР-полноты задачи 3-ВЫП (рассмотреть случаи й ( 3). 2. Универсальность задач нэ класса 1э1РС (г1Р-полных задач) состоит в том, что основные нерешенные вопросы для класса 11Р (ыедетерминированно полиномиальных задач) достаточно разрешить хотя бы для одной ХР-полной задачи, чтобы получить ответ для всего класса ХР. Кроме утверждения 6 здесь также важно Утвкгждкник 10.

Если для некоторой г1Р-полной задачи П дополнительная к ней П принадлежит классу ЯР, то ХР = со-г1Р. 16 Докязятвльотво. Так как П Е ИРС, то 'ФП' Е ЯР П' ое П, отсюда и П ое П (полиномиальное сведение осуществляется той же функцией — см. определение 6).