Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 70
Текст из файла (страница 70)
МИНИМАУ! ЬНОЕ ОСТОВНОЕ ДЕРЕВО Даны связный граф 0=--(У, Е), функция стоимости й, определенная на множестве Е, и целое число Е. Выяснить, существует ли остовное дерево з графе 0 со стоимостью Е или меньше (см. гл, 12), Все эти задачи принадлежат к классу Р. В каждом случае для любой индивидуальной задачи существует эффективный способ узнать, будет ответом да или нет. Введем ~еперь класс )х'Р, более обширный на вид класс задач распознавания.
Для того чтобы задача содержалась в л)Р, мы не требуем, чтобы оэвет в каждой индивидуальной задаче мог быть получен за полиномиальное время с помощью некоторого алгоритма. Мы требуем просто, чтобы в том случае, когда а индивидуальной задаче х ответ ди, существовало бы краткое (т. е, с длиной, ограниченной полиномом от размера х) удостоверение для х, справедливость которого можно было бы проверить за полиномнальное время. Пример 15.5.
Рассмотрим вариант распознавания для задачи о максимальной клике: КЛИКА Даны граф 0=(У, Е) и целое число к. Выяснить, существует лн в данном графе клика (т. е. полностью связанное подмножество множества У) размера к. г.а. ((ласси Р и и Р Не ясно, содержится ли КЛИКА в Р. Очевидный путь решения этой задачи мог бы состоять в проверке для всех ('ь') подмножеств множества $', имеющих мощность й, удовлетворяют ли они требованиям задачи. В результате, конечно, оказывается, что имеется экспоненциальное число таких множеств. В действительности для этой задачи не известно полиномиального алгоритма.
Тем не менее КЛИКА входит в )т'Р. Чтобы понять это, предположим, что иам дана индивидуальная задача КЛИКА с ответом да; другими словами, граф 6=(г', Е) и целое число Й, такие, что в 6 имеется клика С мощности й. Тогда для этой индивидуальной задачи имеется совсем короткое удостоверение, а именно список вершин клики С. Справедливость этого удостоверения можно проверить эффективно, так как нужно проверить только, что С действительно содержит й вершин и что все эти вершины действительно связаны ребрами из Е.
Д Эти идеи можно формализовать следующим образом. Пусть В— фиксированный конечный алфавит н й — выделенный символ в Х. (Символ $ отмечает конец входа и начало удостоверения.) Если х — строка символов из Х, то ее длина — число символов в ней— обозначается через 1х). Определение 16.1. Будем говорить, что задача распознавания А входит в класс й(Р, если существуют полипом р(п) и алгоритм А (алгорипш проверки удоспюагргния), такие, что выполняется следующее свойство: строка х является индивидуальной задачей задачи А с ответом да в том и только в том случае, если существует такая строка с(х) (удоаповергниг) символов из В, что )с(х) 1(р(1х~), и алгоритм А, получая на вход х$с(х), приходит к ответу да после не более р()х~) шагов.
() Пример 16.6 (продолжение). Если в нашем примере задачи КЛИКА х представляет индивидуальную вадачу (6, й) с ответом да, то удостоверением с(х) для х могло бы быть представление списка вершин подходящей клики С. Алгоритм проверки удостоверения проверяет, действительно ли х представляет грвф 6 и целое число й, действительно ли с(х) — множество вершин С, )С~=6 и для каждой пары и, о вершин иа С существует ребро в 6. В качестве поли- нома р(п) можно взять 2п'. Е) Пример 16.6. Следующая задача нам хорошо известна.
ЗАДАЧА КОММИВОЯЖЕРА (ЗК) Даны целое число и, симметричная (пхп)-матрица ~Я с неотрицательными целочисленными элементами и целое чиело Т., Требуется определить, существует ли такая циклическая пере~ч~~я становка (обход) т, что ~1„,дмп1~Ь. Эта задача лежит в ИР, поскольку если дана индивидуальная ЗК (л, '1ао1, Е) с ответом да, то можно очень легко дока.
Рл. 15. УР-полные задачи зать этот факт, представив подходящий обход. Удостоверением для такой индивидуальной задачи мог бы служить код обхода т, удовлетворяющего неравенству ~г,йнш(). Алгоритм й проверял бы, являются ли и, С и [й;Д подходящими, действительно ли т †обх и его длина не превосходит 1.. Д Пример 15.7. Задача ВЪ|ПОЛНИМОСТЪ, рассмотренная в гл. 13, лежгп в )т'Р. Если дано выполнимое множество дизъюнктов С,,..., С„„содержащих булевы переменные х„..., х„, то подходящим удостоверением может служить набор значений истинности, представленный в виде вектора из (О, 1)". Алгоритм проверки удостоверения будет просто проверять, что С„..., С вЂ” это правильные дизъюнкты, содержащие и переменных, и что все дизъюнкты принимают значение истина на наборе значений истинности из удостоверения. П Пример 15.8.
Рассмотрим следующий вариант распознавания задачи целочисленного линейного программирования (ЦЛП). ЦЛП Даны целочисленная (тнп)-матрица А и целочисленный т-вектор о. Выяснить, существует ли целочисленный и-вектор х, такой, что Ах= й, х>0. Отметим, что при преобразовании задачи целочисленного линейного программирования в соответствующий вариант распознавания нам не пспребовалось явно вводить целое число Е и иеравенс1во с'х |., что мы обычно делали при ~аком преобразовании. Это связано с ~ем, что такое неравенство можно преобразовать в равенсчво, добавляя переменную недостатка, и включить это равенство в систему Ах=-о. Задача распознавания ЦЛП лежит в ИР.
Чтобы показать это, вспомним георему 1ЗА, которая утверждает, что если задача целочисленного линейного программирования имеет допустимое решение, то она имеет решение, в котором все компоненты не превосходят Мл=п (та,)' '(!+а,). Такое ограниченное решение может служить кратким удостоверением для индивидуальной задачи ЦЛП с ответом да, так как длина его двоичного представления, как и требуется, полиномиальна относительно размера входа. () 3ажно отметить, что для установления принадлежности некоторой задачи к !4Р не нужно объяснять, как эффективно вычислить удостоверение с(х) по входу х.
Необходимо просто показать суп(ествоеанае по крайней мере одной такой строки для каждого х. Заметим, что Р является подмножеством й!Р. Другими словами, для любой эффективно решаемой задачи можно строить краткие удостоверения. Чтобы понять это, предположим, что для задачи А существует полииомиальный алгоритм йл. Если х — индивидуальная задача задачи А с ответом да, то алгоритм Ал, примененный к х, через полиномиальное число шагов выдает ответ да. Зались работы алгоритма л(л при входе х является подходящим удостовере- 361 !5.4. Полиномиолвныв сведения нием с(х), Действительно, для проверки с(х) достаточно проверить, что это правильное выполнение алгоритма игл, напомним, что по определению с(х) полиномиально по длине. Таким образом, если А Е Р, то А Е ГУР.
Но почему ХР— интересный класс задач распознавания? Вопервых, он содержит класс задач Р, очень нас устраивающий. Во-вторых, он содержит многие интересующие нас задачи, принадлежность которых к классу Р находится под сомнением. Г1римерами являются задачи ЗК, ЦЛП, КЛИКА и ГАМИЛЬТОНОВ ЦИКЛ. Фактически можно сказать, что варианты распознавания всех разумных комбинатор ных задач оптимизации лежат в с|Р, Для обоснования этого напомним, что цель комбинаторных задач оптимизации состоит в построении оптимальных объектов, таких, как обходы, маршруты, множества вершин, разбиения и списки целых чисел. Поэтому есть все основания ожидать, что если найдено оп гимальное решение, то его можно кратко записать, и оно может служить в качестве удостоверения для варианта распознавания.
Нельзя надеяться построить нечто оптимальное, чего абсолютно нельзя было бы построить за разумное время. Поэтому класс й(Р очень естественно появляется при изучении сложности комбинаторных задач оптимизации. А является ли Р собственным подмножеством в НР или Р и е?Р совпадаюз? Если бы последнее было верным, то многие проблемы, известные своей трудностью,— например, ЗК, КЛИКА, ЦЛП и ВЪ|ПОЛНИМОСТЬ вЂ” входили бы в Р и, следовательно, были бы (по-видимому) простыми.
В настоящее время широко расирос1ранеио мнение, что Р является собственным подмножеством в А'Р Пока не известно формального доказательства этого факта, и ~ак называемая проблема Р=МР является сейчас наиболее важнгим зеорезическнм вопросом, стоящим перед специалистами по вычислительным наукам. Однако, несмотря на отсутствие доказательства в ту нли иную сторону, некоторый свет пролит иа эту тайну. Принципиальным математическим инструментом этих исследований явилось понятие сведения, которое мы сейчас рассмотрим.
15.4 Попиномиаиьные сведения Часто оказывается, что решение одной вычислительной задачи становится простым, если допустить, что имеется эффективный алгоритм для решения другой задачи. Например, алгоритм для нахождения максимального потока в сети, представленный на рис. 9.13, использует в качестве подпрограммы умный алгоритм для нахождения тупикового потока в слоистой сети. Аналогично, в Э 12.6 мы видели, что ориентированный вариант задачи ГАМИЛЬТОНОВ ПУТЬ можно решить за полиномиальное время, если имеется эф фективный алгоритм для задачи о пересечении трех ма~роидов л, (В, г!Ртзлные задачи Наконец, в гл. !3 было отмечено, что если бы существовал полиномиальный алгоритм для задачи ЦЛП, то можно было бы эффективно решить задачу ВЫПОЛНИМОСТЬ и много других задач.
Эта достаточно общая ситуация оправдывает следующее формальное определение. Определение !5.2. Пусть А, и А, — задачи распознавания (т. е. задачи с ответами да — нет). Будем говорить, что А, сводится за полиномиальное время к А, тогда и только тогда, когда существует полиномиальный алгоритм А, для А„использующий несколько раз в качестве подпрограммы с единичной стоимостью (гипотетический) алгоритм А, для А,. Будем называть А, нолиномиальным сведением А, к А,. ( ! Наиболее важным в данном выше определении является выражение с единичной стоимостью. Под этим имеется в виду, что алгоритм А, рассматривается как единый оператор, для выполнения которого требуется единица времени.
Естественно, это предположение почти всегда очень нереалистично. Поэтому интересно следующее предложение, которое связывает эту чисто гипотетическую ситуацию с реальной вычислительной сложностью. Предложение !5А. Если А, полиномиально сводится к А, и существует полиномиальный алгоритм для А „ то существует полиномиальный алгоритм для Аь Доказательство. Пусть р!(я) и р,(п) — полиномы, ограничивающие сложность алгоритмов Аг (опять в предположении, что вызов А, имеет единичную стоимость) и А,, Тогда действительная сложность алгоритма А, для входа размера я при условии, что каждый вызов А, стоит столько, сколько требуется времени для выполнения А, с текущими параметрами, ограничена величиной р (л) =р, (я) р, (р, (я)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
