В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов, страница 68

Определим теперь МР как класс всех распозпавательных задач, недетерминированно разрешимых за полипомиальное время. Нетрудно видеть, что Р':-)УР. Действительно, полиномиальный алгоритм решения всякой задачи из Р моншо превратить в полиномиальный алгоритм вида Ф«, добавив оператор В((ь )з) так, чтобы он ни разу не срабатывал. При этом в качестве «,» моя«но взять произвольную последовательность, например, состоящую из одного элемента. Класс ВР чрезвычайно широк.

Например, большинству задач, встречающихся в предыдущих главах, можно «естественным» образом сопоставить распознавательные задачи. При этом окажется, что почти все они принадлеи«ат МР. В качестве примера доказательства пр»«падлежности задачи к МР рассмотрим задачу об изоморфпом подграфе, которую здесь сформулируем в следующем виде. Даны два графа ь»1 и 6», причем Уь»1 = Уь»» = У, Установить, существует ли такая подстановка з: У- У, 367 для которой истинна пмпликацпн (ин ~н Еб~) ~ (г (и) г (и) ~ Еб«) . Очевидно, что ограничение РС~ =- РС«, которого пег в определении, приведенном в $ 27, несущественно. Удобно рассматривать зту задачу в матричной постановке.

Пусть У=-(1, 2, ..., и), Л~ п Л« — матрицы смежности графов 6~ н Сз соответственно. Обозначим через о матрицу подстановки г (см. з 6). Теперь задачу об изоморфном подграфе можно сформулировать так: определить, существуег лп такая матрица подстановки Я, что все одпппцы матрицы БА~Я ' содержатся среди единиц матрицы Лк т. е. что матрица (Аз — БА~Я ') неотрицательпа. Недетермпппровапный алгоритм Ф для решения этой задачи выглядит следующим образом. 1. Выполнить пп. 2 — 4 для всех й = 1, и' и перейти к п. 5. 2. В(3,4). 3. 1„:=О.

1л- 5. Яе.'=1ч. пы для всех 1, 1 =1, и. 6. А':=БА,Б-'. 7. Если матрица Аз — А' неотрицательна, то конец и ответ «да». Иначе — конец. Напомним, что Яе — элемент матрицы Я, занимающий позицию (1, 1). Полая«ем теперь, как выбирать угадывающую последовательность ф Рассмотрим произвольный вход задачи, имеющий ответ «да». Это — нара симметрических (О, 1)- матриц Л~ и Л., для которой существует такая матрица подстановки Я, что Аз — БА~Я ' — неотрицательная матрица. Заменим в матрице Я 0 на 3 и 1 на 4 и в качестве Д возьмем последовательность элементов атой новой матрицы, выписанных по строкам. Работа алгоритма Ф«состоит из двух этапов. На первом этапе (пп.

1 — 5) с помощью Ч строится матрица подстановки, обеспечивающая изоморфное вложение. Содержанием второго этапа (пп. 6, 7) является проверка того, что матрица Я обладает нужным свойством. Полиномнальвость алгоритма .вс«очевидна. Напомним, что частными случаями задачи об изоморфном подграфе являются задачи об изоморфизма графов, о существовании в графе гамильтонова цикла или клики заданного размера и ряд других. Таким образом, 368 попутно установлена принадлежность всех этих задач к классу ХР. Доказательство этого свойства для других графовых задач проводится, как правило, столь же просто. При атом работа алгоритма .Ф«, так же как и в предыдущем случае, распадается на два атапа: 1) построение некоторого варианта, 2) проверка того, что этот вариант подходящий. Например, в задаче о Й-раскраске вершин графа такой алгоритм сначала припишет вершинам графа нужные цвета, а затем проверит, что любые две вершины одного цвета не смежны.

Тот факт, что большинство «естественных» задач входит в класс УР, свидетельствует о чрезвычайной вал<- ности вопроса: совпадают ли классы Р и МР? Эта не решенная до сих пор проблема считается важнейшей в науке о вычислениях. Большинство исследователей склоняется к мнению, что РчьйуР. На первый взгляд ситуация Рть1»*Р не лишает нас возможности получить в будущем полиномиальный алгоритм решения какой-либо из задач, названных нами «трудными». Однако это не так. Как оказалось, из Рч«МР следует, что ни одна иэ этих «трудных» задач не имеет полиномиального алгоритма, а из существования такого алгоритма для одной из них следует, что Р = ФР.

Изложение соответствующих результатов опирается на понятие сводимости одной задачи к другой. Предложение «задача А сводится к задаче В» означает, в общепринятом смысле, что из решения задачи В можно получить решение задачи А. Нам необходимо уточнить это понятие так, чтобы оно учитывало вычислительные затраты, связанные с получением решения одной задачи из решения другой.

Пусть существует полиномпальный алгоритм Р, кото- рый, будучи примененным ко всякому входу 1 задачи А, строит некоторый вход Р(1) задачи В. Если при этом вход 1 имеет ответ «да» тогда и только тогда, когда от- вет «да» имеет вход Р(1), то говорят, что задача А ло-- линоииально сводится к задаче В, и пишут А « В. По- скольку своднмостей, отличных от полнномнальной, мы не рассматриваем, то слово «полиномиально» в дальнейшем будем опускать и говорить просто «А сводится к В». Нетрудно показать, что если задача А сводится к задаче В и В я Р, то и А ш Р. Действительно, пусть Ф— алгоритм решения задачи В и полиномы р~(п), р»(и) таковы, что 0(р~(п) ) и 0(р»(п) ) — сложности алгоритмов Р и .Ф соответственно. Рассмотрим теперь алгоритм 24 в, ь, квелвче» э л».

369 .Ф' решения задачи А, состоящей из двух этапов. На первом этапе вход 1 задачи А преобразуется алгоритмом Р во вход 1т(1) задачи В. На втором этапе алгоритм .Ф применяется ко входу Р (1). Согласно определению Р, алгоритм А' сообщит ответ «да» тогда и только тогда, когда вход 1 имеет ответ «да», т. е. алгоритм «б' действительно решает задачу А. Выясним теперь его сложность. Если длина 1 равна и, то Р(1) будет построен за время 0(р~(п)), и его длина — 0(р~(п)). При этом алгоритм с»», будучи примененным ко входу Г(1), затратит время 0(р»(р,(п))). Таким образом, сложность алгоритма ,»1' есть 0(р1(п)+ р»(р~(п))), Поскольку суперпозиция и сумма полиномов также являются полиномами, то,Ф вЂ” полнномиальный алгоритм.

Точно так же можно показать, что из А ы В и В ы С следует А С. Задачу А назовем ХР-полной, если А ДАХР и любая задача из ХР сводится к А. Из этого определенна и предыдущих рассмотрений сразу следует, что Р = ХР, если хотя бы одна ХР-полная задача входит в Р. Говоря неформально, каждая ХР-полная задача «не проще», чем любая задача нз ХР.

Поэтому, доказав ХР-полноту некоторой задачи, мы получаем веские основания считать ее трудной. Для доказательства ХР-полноты задачи достаточно установить ее принадлежность к ХР и показать, что к ней сводится некоторая ХР-полная задача. Чтобы воспользоваться этой схемой, надо иметь в распоряжении хотя бы одну ХР-полную задачу. Первой задачей, относительно которой было показано, что она является ХР-полной, была задача о выполнимости. Пусть хь х», х», ...— булевы переменные, принимающие значения «истнна» нли «лоя«ь», и хи хы х»,...— их отрицания.

Те и другие в совокупности называются литералами. Пусть символы Ч и Д обозначают булевы операции дизъюнкции и конъюнкции соответственно. Формула и~ Ч и» Ч... Ч и„называется элементарной дивьюнкцией, если ин ип ..., и„— литералы. Пусть Сн С», ... ..., С, — элементарные дизыонкции. Тогда выражение вида Сг /~ С, /~ ... /~ Ср называется булевым выражением в конъюнктивной нормальной форме. Булево выражение называется выполнимым, еесли входящим в него переменным можно так присвоить значения «истина» или «ложь», что значением выражения будет «истина».

Не все выражения являются выполнимыми. Например, 370 булево выражение (хь 'ь/ х,) /~ (х, ьс' хз) /ь (х, ь/ хз) выполнимо, а выражение (хь 'ь/ хь) Л (хь ь/ хь) /ь (хь с/ ть) /'ь /~ (х, ~/ хь) не выполнимо. Задача о выполнимости (ВЫПОЛНИМОСТЬ) состоит в оиределепнн, является ли данное булево выражение в конъюнььтььвной нормальной форме выполнимым. Следующая теорема, приводимая здесь без доказательства, лежит в основе теории АсР-полнотьь. Теорема (С. Кук, 1971 г.).

Задаса ВЫПОЛНИМОСТЬ является /ь/Р-полной. В настоящее время известен значительный (и интенсивно пополняющийся) список сьР-полнььх задач. В этом списке находятся почти все задачи, получившие ранее репутацию трудных для алгоритмического решения. Ниже приведены только те из них, с которыми мы сталкивались в предыдущих главах. Некоторые /Ь/Р-польььье задачи. КЛИКА: Даны граф 6 и натуральное число Й. Определить, содержит лн граф 6 клику мощности Й. НЕЗАВИСИМОСТЬ: Даны граф 6 и натуральное число Й. Определить, содержит ли граф 6 независимое Й-элементное множество вершин. ИЗОМОРФНЫИ ПОДГРАФ: Даны два графа 6ь = =()т, Ес) н 6ь =()т, Еь), Определить, существует ли подстановка в: У вЂ” ь', для которой истинна импликация (ии ьн Е,) =.

(г (и) в(и) ~ Ез). ВЕРШИННОЕ ПОКРЫТИЕ: Даны граф 6 н натуральное число Й. Определить, существует лн в графе 6 вершинное покрытие мощности не более Й. ДОМИНИРУЮЩЕЕ МНО)КЕСТВО: Даны граф 6 и натуральное число Й. Определить, существует лн в графе 6 доминирующее множество мощности не менее Й. ГАМИЛЬТОНОВ ЦИКЛ: Дан граф 6. Определить, содержит ли граф 6 гамильтонов цикл. ЯДРО: Дан ориентированный граф 6. Определить, содержит ли граф 6 ядро. ВЕР1ПИННАЯ (РЕБЕРНАЯ) РАСКРАСКА: Даны граф 6 и натуральное число Й.

Определить, существует ли правильная Й-раскраска вершин (ребер) графа 6. Рассмотрим в качестве примера доказательство АсР- полноты задачи КЛИКА. Пусть Ьь — граф, у которого некоторые Й вершин образуют клику, а остальные и — Й вЂ” изолированные вершины. Ранее мы установили, что задача ИЗОМОРФНЫЙ ПОДГРАФ принадлежит 371 МР.

Если в этой задаче положить С»= С, где С вЂ” граф, фигурирующий в формулировке задачи КЛИКА, а в качестве С~ выбрать граф Вп то получим задачу 1(ЛИКА. Следовательно, задача КЛИКА прина, лежит 3Р. Покажем теперь, что ВЫПОЛП11МООТЬ с КЛИКА.

Пусть В = С~ Ч С» Ч... Ч С вЂ” произвольное булево выражение в конъюнктивной нормальной форме, (иъ и», ... ..., и»1 — мнон ество входящпх в него литералов. Будем обозначать через С«мнол«естес литералов, входящих в элементарную дизъюнкцию Сь Поставим в соответствие выражению В граф 6 по следующему правилу: РС = (пм. 'и» е= С»), ВС = (пяпы, и«Ф ию 1Ф 1).