ГЛАВА 10

Труднорешаемые проблемы

Обсуждение вычислимости переносится на уровень ее эффективности или неэффектив­ности. Предметом изучения становятся разрешимые проблемы, и нас интересует, какие из них можно решить на машинах Тьюринга за время, полиномиально зависящее от раз­мера входных данных. Напомним два важных факта из раздела 8.6.3.

Проблемы, разрешимые за полиномиальное время на обычном компьютере, — это именно те проблемы, которые разрешимы за такое же время с помощью ма­шины Тьюринга.

Практика показывает, что разделение проблем на разрешимые за полиномиальное время и требующие экспоненциального или большего времени, является фундамен­тальным. Полиномиальное время решения реальных задач, как правило, является приемлемым, тогда как задачи, требующие экспоненциального времени, практиче­ски (за приемлемое время) неразрешимы, за исключением небольших экземпляров.

В этой главе изучается теория «труднорешаемости», т.е. методы доказательства не­разрешимости проблем за полиномиальное время. Вначале рассматривается конкретный вопрос выполнимости булевой формулы, т.е. является ли она истинной для некоторого набора значений ИСТИНА и ЛОЖЬ ее переменных. Эта проблема играет в теории сложности такую же роль, как L„ и ПСП для неразрешимых проблем. Вначале мы дока­жем «теорему Кука», которая означает, что проблему выполнимости булевых формул нельзя разрешить за полиномиальное время. Затем покажем, как свести эту проблему ко многим другим, доказывая тем самым их труднорешаемость.

При изучении полиномиальной разрешимости проблем изменяется понятие сведения. Теперь уже недостаточно просто наличия алгоритма, который переводит экземпляры од­ной проблемы в экземпляры другой. Алгоритм перевода сам по себе должен занимать не больше времени, чем полиномиальное, иначе сведение не позволит сделать вывод, что доказываемая проблема труднорешаема, даже если исходная проблема была таковой. Таким образом, в первом разделе вводится понятие «полиномиальной сводимости» (сводимости за полиномиальное время).

Между выводами, которые дают теории неразрешимости и труднорешаемости, существует еще одно принципиальное различие. Доказательства неразрешимости, приведенные в главе 9, неопровержимы. Они основаны только на определении ма­шины Тьюринга и общих математических принципах. В отличие от них, все приво­димые здесь результаты о труднорешаемости проблем основаны на недоказанном, но безоговорочно принимаемом на веру предположении, которое обычно называется предположением V Ф J\tP.

Итак, предполагается, что класс проблем, разрешимых недетерминированными МТ за полиномиальное время, содержит, по крайней мере, несколько проблем, которые нельзя решить за полиномиальное время детерминированными МТ (даже если для последних до­пускается более высокая степень полинома). Существуют буквально тысячи проблем, при­надлежность которых данной категории практически не вызывает сомнений, поскольку они легко разрешимы с помощью НМТ с полиномиальным временем, но для их решения не известно ни одной ДМТ (или, что то же самое, компьютерной программы) с полиноми­альным временем. Более того, важным следствием теории труднорешаемости является то, что либо все эти проблемы имеют детерминированные решения с полиномиальным време­нем — решения, ускользавшие от нас в течение целых столетий, либо таких решений не имеет ни одна из них, и они действительно требуют экспоненциального времени.

10.1. Классы V и MV

В этом разделе вводятся основные понятия теории сложности: классы V и NV про­блем, разрешимых за полиномиальное время, соответственно, детерминированными и недетерминированными МТ, а также метод полиномиального сведения. Кроме того, оп­ределяется понятие «NP-полноты» — свойства, которым обладают некоторые проблемы из MV. Они, как минимум, так же трудны (в пределах полиномиальной зависимости вре­мени), как любая проблема из класса NV.

Проблемы, разрешимые за полиномиальное время

Говорят, что машина Тьюринга М имеет временную сложность Т\п) (или «время ра­боты Т(п)»), если, обрабатывая вход w длины п, М делает не более Т(п) переходов и оста­навливается независимо от того, допущен вход или нет. Это определение применимо к любой функции Т(п), например, Т(п) = 50и² или Т(п) = 3″ + 5и⁴. Нас будет интересовать, главным образом, случай, когда Т(п) является полиномом относительно п. Мы говорим, что язык L принадлежит классу V, если существует полином Т(п), при котором L = ЦМ) для некоторой детерминированной МТ Мс временной сложностью Т(п).

Пример: алгоритм Крускала

Читатель, вероятно, уже хорошо знаком со многими проблемами, имеющими эффек­тивные решения. Некоторые из них, возможно, изучались в курсе по структурам данных и алгоритмам. Как правило, эти проблемы принадлежат классу V. Рассмотрим одну та­кую проблему: поиск в графе остовного дерева минимального веса (ОДМВ).

Есть ли что-то между полиномами и экспонентами?

В дальнейшем, как и во вступлении, мы часто будем действовать так, как если бы время работы любой программы было либо полиномиальным (0(п^к) для некоторого целого числа к), либо экспоненциальным (<9(2^СП) для некоторой константы с > 0) или более того.

Известные из практики алгоритмы решения наиболее распространенных проблем, как правило, относятся к одной из этих категорий. Когда мы говорим об экспоненциаль­ном времени, то всегда имеем в виду «время работы, которое больше любого поли­нома». Однако существуют времена работы программ, лежащие между полиномиаль­ным и экспоненциальным временем.

Примером функции, находящейся между полиномами и экспонентами, является функция и¹⁰®²«. Эта функция с ростом п увеличивается быстрее любого полинома, по­скольку log п в конце концов (при больших п) превосходит любую константу к. С дру­гой стороны, я’⁰®²» = 2^(ioBl«^,: (если это неочевидно, возьмите логарифм обеих частей). Эта функция растет медленнее, чем 2^СП при любой константе с > 0, поскольку сп в конце концов превышает (log₂п)², какой бы малой ни была с.

Неформально графы представляются как диаграммы, наподобие изображенной на рис. 10.1. У них есть узлы, которые в данном примере графа пронумерованы 1-4, и реб­ра, соединяющие некоторые пары узлов. Каждое ребро имеет целочисленный вес. Ос- товное дерево — это подмножество ребер, с помощью которых соединены все узлы, но циклы отсутствуют. Пример остовного дерева показан на рис. 10.1 — это три ребра, вы­деленные жирными линиями. Остовное дерево минимального веса— это дерево наи­меньшего общего веса среди всех остовных деревьев.

■Рис. 10.1. Граф, в котором остовное дерево минимального веса выделено жирными линиями

Для нахождения ОДМВ существует хорошо известный «жадный» алгоритм, который называется алгоритмом Крускала’. Опишем вкратце его основные идеи.

Для каждого узла определяется компонент связности, который содержит этот узел и образован с использованием ребер, выбранных до сих пор. Вначале не выбрано ни одно ребро, так что каждый узел образует отдельный компонент связности.

Среди еще не выбранных ребер рассмотрим ребро минимального веса. Если оно со­единяет два узла, которые в данный момент принадлежат различным компонентам связности, то выполняется следующее:

а)   ребро добавляется в остовное дерево;

б)   связные компоненты сливаются (объединяются) путем замены номера ком­понента у всех узлов одного из них номером другого.

Если же выбранное ребро соединяет узлы из одного и того же компонента, то это ребро не принадлежит остовному дереву; его добавление привело бы к образованию цикла.

Выбор ребер продолжается до тех пор, пока мы не выберем все ребра, или число ре­бер, выбранных в остовное дерево, не станет на единицу меньше общего числа уз­лов. Заметим, что в последнем случае все узлы должны принадлежать одному ком­поненту связности, и процесс выбора ребер можно прекратить.

Пример 10.1. В графе на рис. 10.1 сначала рассматривается ребро (1, 3), поскольку оно имеет минимальный вес — 10. Так как вначале 1 и 3 принадлежат разным компонен­там, это ребро принимается, а узлам 1 и 3 приписывается один и тот же номер компонен­та, скажем, «компонент 1». Следующее по порядку возрастания веса ребро — (2, 3) с ве­сом 12. Поскольку 2 и 3 принадлежат разным компонентам, то это ребро принимается, и 2 добавляется в «компонент 1». Третье ребро -— (1, 2) с весом 15. Но узлы 1 и 2 уже на­ходятся в одном компоненте, поэтому данное ребро отбрасывается, и мы переходим к четвертому ребру— (3, 4). Поскольку 4 не содержится в «компоненте 1», данное ребро принимается. Теперь у нас есть остовное дерево из трех ребер, и можно остановиться. □ Этот алгоритм обработки графа с т узлами и е ребрами можно реализовать (с помо­щью компьютера, а не машины Тьюринга) за время 0(т + е log е). Более простая реали­зация имеет е этапов. Номер компонента каждого узла хранится в некоторой таблице. Выбор ребра наименьшего веса среди оставшихся занимает время О(е), а поиск компо­нентов, в которых находятся узлы, связанные этим ребром, — 0(т). Если эти узлы при­надлежат различным компонентам, то на просмотр таблицы для объединения всех узлов с соответствующими номерами нужно время 0(т). Таким образом, общее время работы этого алгоритма — 0(е(е + т)). Это время полиномиально зависит от «размера» входных данных, в качестве которого можно неформально выбрать сумму ей т.

¹ J. В. Kruskal Jr., «On the shortest spanning subtree of a graph and the traveling salesman problem», Proc. AMS 7:1 (1956), pp.48-50.

При перенесении изложенных идей на машины Тьюринга возникают следующие вопросы.

Выход алгоритмов разрешения различных проблем может иметь много разных форм, например, список ребер ОДМВ. Проблемы же, решаемые машинами Тью­ринга, можно интерпретировать только как языки, а их выходом может быть только ДА или НЕТ (допустить или отвергнуть). Например, проблему поиска ОДМВ можно перефразировать так: «Для данного графа G и предельного числа W выяснить, имеет ли G остовное дерево с весом не более W1». Может показать­ся, что эту проблему решить легче, чем проблему ОДМВ в знакомой нам форму­лировке, поскольку не нужно даже искать остовное дерево. Однако в рамках тео­рии труднорешаемости нам, как правило, нужно доказать, что проблема трудна (не легка). А из того, что «да/нет»-версия проблемы трудна, следует, что трудна и ее версия, предполагающая полный ответ.

Хотя «размер» графа можно неформально представить себе как число его узлов или ребер, входом МТ является цепочка в некотором конечном алфавите. По­этому такие элементы, фигурирующие в проблеме, как узлы и ребра, должны быть подходящим образом закодированы. Выполняя это требование, получаем в результате цепочки, длина которых несколько превышает предполагаемый «размер» входа. Однако есть две причины проигнорировать эту разницу.

Размеры входной цепочки МТ и входа неформальной проблемы всегда отличаются не более, чем малым сомножителем, обычно — логарифмом размера входных дан­ных. Таким образом, все, что делается за полиномиальное время с использованием одной меры, можно сделать за полиномиальное время, используя другую меру.

Длина цепочки, представляющей вход, — в действительности более точная мера числа байтов, которые должен прочитать реальный компьютер, обрабатывая свой вход. Например, если узел задается целым числом, то количество байтов, необходи­мых для представления этого числа, пропорционально его логарифму, а это не «1 байт на каждый узел», как можно было бы предположить при неформальном подсче­те размера входа.

Пример 10.2. Рассмотрим код для графов и предельных весов, который может быть

входом для проблемы ОДМВ. В коде используются пять символов: 0, 1, левая и правая

скобки, а также запятая.

Припишем всем узлам целые числа от 1 до т.

В начало кода поместим значения т и предельного веса Wb двоичной системе счис­ления, разделенные запятой.

Если существует ребро, соединяющее узлы i иу и имеющее вес w, то в код записыва­ется тройка (i,j, w), где целые числа /, j и w кодируются в двоичном виде. Порядок записи узлов ребра и порядок ребер в графе не играют роли.

Таким образом, один из возможных кодов графа на рис. 10.1 с предельным весом W= 40 имеет вид

100, 101000(1, 10, 1111)(1, 11, 1010)(10, 11, 1100)(10, 100, 10100>( 11, 100, 10010).

□

Если кодировать входы проблемы ОДМВ так, как в примере 10.2, то вход длины п может представлять максимум O(n/\ogn) ребер. Если число ребер очень мало, то число узлов т может быть экспоненциальным относительно п. Однако если число ребер е меньше т- 1, то граф не может быть связным, и независимо от того, каковы эти ребра, не имеет ОДМВ. Следовательно, если количество узлов превосходит число «/log и, то нет никакой необходимости запускать алгоритм Крускала— мы просто говорим: «нет, ос- товного дерева с таким весом не существует».

Итак, пусть у нас есть верхняя граница времени работы алгоритма Крускала, вы­ражаемая в виде функции от т и е, например, как найденная выше верхняя граница 0(е(е + т)). Можно изменить т и е на п и сказать, что время работы выражается функцией от длины входа п, имеющей вид 0(п(п + я)) или 0(п²). В действительно­сти, более удачная реализация алгоритма Крускала требует времени 0(п log п), но сейчас это не важно.

Представленный алгоритм Крускала предназначен для реализации на языке програм­мирования с такими удобными структурами данных, как массивы и указатели, но в каче­стве модели вычислений мы используем машины Тьюринга. Тем не менее, описанную выше версию алгоритма можно реализовать за 0(п²) шагов на многоленточной машине Тьюринга. Дополнительные ленты используются для выполнения нескольких вспомога­тельных задач.

На одной из лент можно хранить информацию об узлах и их текущих номерах ком­понентов. Длина такой таблицы составит О(п).

Еще одна лента может применяться в процессе просмотра входной ленты для хране­ния информации о ребре, имеющем на данный момент наименьший вес среди ребер, не помеченных как «использованные» (выбранные). С помощью второй дорожки входной ленты можно отмечать те ребра, которые были выбраны в качестве ребер наименьшего веса на одном из предыдущих этапов работы алгоритма. Поиск непо­меченного ребра наименьшего веса занимает время 0(п), поскольку каждое ребро рассматривается лишь один раз, и сравнить вес можно, просматривая двоичные чис­ла линейно, справа налево.

Если ребро на некотором этапе выбрано, то соответствующие два узла помещаются на ленту. Чтобы установить компоненты этих двух узлов, нужно просмотреть табли­цу узлов и компонентов. Это займет 0(п) времени.

Еще одна лента может хранить информацию об объединяемых компонентах i и j, когда найденное ребро соединяет различающиеся на данный момент компоненты. В этом

случае просматривается таблица узлов и компонентов, и для каждого узла из компо­нента i номер компонента меняется на j. Эта процедура также занимает О(п) времени.

Теперь нетрудно самостоятельно завершить доказательство, что на многоленточной МТ каждый этап работы алгоритма может быть выполнен за время О(п). Поскольку чис­ло этапов е не превышает я, делаем вывод, что времени 0(п²) достаточно для многолен­точной МТ. Теперь вспомним теорему 8.10, утверждавшую, что работу, которую много­ленточная МТ выполняет за s шагов, можно выполнить на одноленточной МТ за 0(s²) шагов. Таким образом, если многоленточной МТ требуется сделать 0(п²) шагов, то мож­но построить одноленточную МТ, которая делает то же самое за 0((п²)²) = 0(п^А) шагов. Следовательно, «да/нет»-версия проблемы ОДМВ («имеет ли граф G ОДМВ с общим ве­сом не более W7») принадлежит V.

• Недетерминированное полиномиальное время

Фундаментальный класс проблем в изучении труднорешаемости образован пробле­мами, разрешимыми с помощью недетерминированной МТ за полиномиальное время. Формально, мы говорим, что язык L принадлежит классу MV (недетерминированный по­линомиальный), если существуют недетерминированная МТ М и полиномиальная вре­менная сложность Т(п), для которых L = L(M), и у М нет последовательностей переходов длиной более Т(п) при обработке входа длины п.

Поскольку всякая детерминированная МТ представляет собой недетерминированную МТ, у которой нет возможности выбора переходов, то V с MV. Однако оказывается, что в MV содержится множество проблем, не принадлежащих V. Интуиция подсказывает: причина в том, что НМТ с полиномиальным временем работы имеет возможность уга­дывать экспоненциальное число решений проблемы и проверять «параллельно» каждое из них за полиномиальное время. И все-таки,

• одним из самых серьезных нерешенных вопросов математики является вопрос о том, верно ли, что V = MP, т.е. все, что с помощью НМТ делается за полиноми­альное время, ДМТ в действительности также может выполнить за полиномиаль­ное время (которое, возможно, выражается полиномом более высокой степени).
• Пример wsMV’. проблема коммивояжера

Для того чтобы осознать, насколько обширен класс AfP, рассмотрим пример проблемы, которая принадлежит классу MP, но, предположительно, не принадлежит V, — проблему коммивояжера (ПКОМ). Вход ПКОМ (как и у ОДМВ) — это граф, каждое ребро которого имеет целочисленный вес (рис. 10.1), а также предельный вес W. Вопрос состоит в том, есть ли в данном графе «гамильтонов цикл» с общим весом, не превышающим W. Гамиль- тонов цикл — это множество ребер, соединяющих узлы в один цикл, причем каждый узел встречается в нем только один раз. Заметим, что число ребер в гамильтоновом цик­ле должно равняться числу узлов графа.

Одна из версий недетерминированной допустимости

Заметим, что мы требовали останова нашей НМТ за полиномиальное время на любой из ветвей (ее работы), независимо от того, допускает она или нет. Можно было бы также установить полиномиальное ограничение во времени Т\п) лишь для тех ветвей, которые ведут к допусканию, т.е. определить NP как класс языков, допускаемых НМТ, которые допускают с помощью хотя бы одной последовательности переходов длиной не более Т(п), где Т(п) — некоторый полином.

Однако в результате мы получили бы тот же самый класс языков, и вот почему. Если нам известно, что М, если вообще допускает, делает это в результате 1\п) переходов, то ее можно модифицировать так, чтобы на отдельной дорожке ленты она вела счет до Т(п) и останавливалась, не допуская, если счет превысит Т(п). Число шагов моди­фицированной М могло бы достигать С)(^г1^й(п)). Но если Т(п) — полином, то и 1²(п) — полином.

В действительности, класс V можно было бы также определить с помощью машин Тьюринга, допускающих за время Т(п), где Т(п) есть некоторый полином. Эти МТ могли бы не останавливаться, не допуская. Но с помощью такой же конструкции, как и для НМТ, мы могли бы модифицировать ДМТ так, чтобы она считала до Т\п) и ос­танавливалась, перейдя эту границу. Время работы такой ДМТ было бы (XT²(н)).

Пример 10.3. Граф, изображенный на рис. 10.1, имеет в действительности лишь один гамильтонов цикл — (1, 2, 4, 3, 1). Его общий вес составляет 15 + 20 + 18 + 10 = 63. Та­ким образом, если W имеет значение 63 или больше, то ответ— «да», а если W < 63, то ответ — «нет».

Однако простота ПКОМ для графа с четырьмя узлами обманчива. В данном графе попросту не может быть более двух различных гамильтоновых циклов, учитывая, что один и тот же цикл может иметь начало в разных узлах и два направления обхода. Но в графе с m узлами число различных циклов достигает 0(ml), факториала числа ш, что превышает 2^ст для любой константы с. □

Оказывается, что любой способ решения ПКОМ включает перебор, по сути, всех циклов и подсчет общего веса каждого из них. Можно поступить умнее, отбросив неко­торые, очевидно неподходящие, варианты. Однако, по всей видимости, при любых на­ших усилиях все равно придется рассматривать экспоненциальное число циклов перед тем, как убедиться в том, что ни один из них не имеет вес меньше предельного W, или отыскать такой цикл.

С другой стороны, если бы у нас был недетерминированный компьютер, то можно было бы «угадать» перестановку узлов и вычислить общий вес цикла, образованного уз­лами в этом порядке. Если бы существовал реальный недетерминированный компьютер, то при обработке входа длины п ни на одной из ветвей ему не пришлось бы сделать бо­лее 0(п) шагов. На многоленточной НМТ перестановку можно угадать за 0(п ) шагов, и столько же времени понадобится для проверки ее общего веса. Таким образом, однолен- точная НМТ может решить ПКОМ за время, не превышающее 0(п⁴). Делаем вывод, что ПКОМ принадлежит классу NP.

10.1.5. Полиномиальные сведения

Основной метод доказательства того, что проблему Р₂ нельзя решить за полиноми­альное время (т.е. Р₂ не принадлежит V), состоит в сведении к ней проблемы P_h относи­тельно которой известно, что она не принадлежит V^[1] Данный подход был представлен на рис. 8.7, который воспроизводится здесь в виде рис. 10.2.

Экземпляр Pi

нет

Рис. 10.2. Повторение картины сведения

Допустим, что мы хотим доказать утверждение: «если Р₂ принадлежит V, то и Pi при­надлежит V’. Поскольку мы утверждаем, что Р/ не принадлежит V, можно будет утвер­ждать, что и Р₂ не принадлежит V. Однако одного лишь существования алгоритма, обо­значенного на рис. 10.2 как «Построение», не достаточно для доказательства нужного нам утверждения.

В самом деле, пусть по входному экземпляру проблемы Pi длиной т алгоритм выра­батывает выходную цепочку длины 2^т, которая подается на вход гипотетическому алго­ритму, решающему Р₂ за полиномиальное время. Если решающий Р₂ алгоритм делает это, скажем, за время 0(п^к), то вход длиной 2^т он обработает за время 0(2^km), экспонен­циальное по т. Таким образом, алгоритм, решающий P_h обрабатывает вход длиной т за время, экспоненциальное по т. Эти факты целиком согласуются с ситуацией, когда Р₂ принадлежит V, а г j — нет.

Даже если алгоритм, переводящий экземпляр Р/ в экземпляр Р₂, всегда вырабатывает экземпляр, длина которого полиномиальна относительно длины входа, то мы все равно можем не добиться желаемого результата. Предположим, что построенный экземпляр Р₂ имеет ту же длину т, что и P_h но сам алгоритм преобразования занимает время, экспо­ненциальное по т, скажем, 0(2^т). Тогда из того, что алгоритм решения Р₂ тратит на об­работку входа длиной п время 0(«^к), следует лишь то, что существует алгоритм решения Pi, которому для обработки входа длиной т нужно время 0(2^Ш + т^к). В этой оценке вре­мени работы учитывается тот факт, что необходимо не только решить итоговый экземп­ляр Р₂, но и получить его. И вновь возможно, что Р₂ принадлежит V, a Pi — нет.

Правильное ограничение, которое необходимо наложить на преобразование Pi в Р₂, состоит в том, что время его выполнения должно полиномиально зависеть от размера входных данных. Отметим, что если при входе длины т преобразование занимает время 0(W), то длина выходного экземпляра Р₂ не может превышать числа совершенных ша­гов, т.е. она не больше crri, где с — некоторая константа. Теперь можно доказать, что ес­ли Р₂ принадлежит V, то и P_t принадлежит V.

Для доказательства предположим, что принадлежность цепочки длины п к Р₂ можно выяснить за время 0(п). Тогда вопрос о принадлежности Р, цепочки длины т можно решить за время Oijrf + (cm^xf )\ слагаемое т^] учитывает время преобразования, а (ст’)^к — время выяснения, является ли результат экземпляром Р₂. Упрощая выражение, видим, что Р/ может быть решена за время 0(т^] + ст^,к). Поскольку с, j и к — константы, это

время зависит от т полиномиально, и, следовательно, Р/ принадлежит V.

Итак, в теории труднорешаемости используются только полиномиальные сведения ((сведения за полиномиальное время). Сведение P_t к Р₂ является полиномиальным, если оно занимает время, полиномиальное по длине входного экземпляра Р/. Как следствие, длина выходного экземпляра Р₂ будет полиномиальной по длине экземпляра Pi.

10.1.6. NP-подные проблемы

Теперь познакомимся с группой проблем, которые являются наиболее известными кандидатами на то, чтобы принадлежать MV, но не принадлежать V. Пусть L — язык (проблема) из класса NP. Говорят, что L является NP-полным, если для него справедли­вы следующие утверждения.

L принадлежит J\fV.

Для всякого языка L’из NPсуществует полиномиальное сведение L’kL.

Как мы увидим, примером NP-полной проблемы является проблема коммивояжера (см. раздел 10.1.4). Предполагается, что V^NV, и, в частности, что все NP-полные про­блемы содержатся в NV — V, поэтому доказательство NP-полноты проблемы можно рас­сматривать как свидетельство того, что она не принадлежит V.

Вначале докажем NP-полноту так называемой проблемы выполнимости булевой формулы (ВЫП), показав, что язык всякой НМТ с полиномиальным временем полино­миально сводится к ВЫП. Имея в распоряжении некоторые NP-полные проблемы, мож­но доказать NP-полноту еще одной, новой проблемы посредством полиномиального све­дения к ней одной из известных проблем. Следующая теорема объясняет, почему такое сведение доказывает, что новая проблема является NP-полной.

Теорема 10.4. Если проблема Pi является NP-полной, и существует полиномиальное сведение P_t к Р₂, то проблема Р₂ также NP-полна.

Доказательство. Нужно показать, что всякий язык L из HV полиномиально сводится к Р₂. Мы знаем, что существует полиномиальное сведение L к Рр, это сведение занимает некоторое полиномиальное время р(п). Поэтому цепочка w из L длиной п преобразуется в цепочку х из Pi, длина которой не превосходит р(п).

Мы также знаем, что существует полиномиальное сведение Р/ к Р₂; пусть это сведение занимает полиномиальное время q(m). Тогда это сведение преобразует х в некоторую це­почку у из Р₂, за время, не превосходящее q(p(n)). Таким образом, преобразование w в у за­нимает времени не более р(п) + q(p(n)), которое является полиномиальным. Следовательно, L полиномиально сводим к Р₂. Поскольку L — произвольный язык из AfV, то мы показали, что все проблемы класса HV полиномиально сводятся к Р₂, т.е. Р₂ является NP-полной. □

NP-трудные проблемы

Некоторые проблемы L трудны настолько, что, хотя и можно доказать, что для них вы­полняется условие 2 из определения NP-полноты (всякий язык из NP сводится к L за полиномиальное время), условие 1 — что L принадлежит MV— мы доказать не можем. Если это так, то L называется NP-трудной. До сих пор в отношении проблем, требую­щих для решения экспоненциального времени, использовался нестрогий термин «труднорешаемая». Вообще говоря, термин «труднорешаемая» в значении «NP-трудная» использовать можно, хотя могут существовать проблемы, требующие экспоненциально­го времени, несмотря на то, что в строгом смысле они не являются NP-трудными. Для доказательства NP-трудности проблемы L достаточно показать высокую вероят­ность того, что L требует экспоненциального или большего времени. Однако если L не принадлежит классу MV, то ее очевидная трудность никак не может служить под­тверждением того, что все NP-полные проблемы трудны, т.е. может выясниться, что V — MV, но при этом L все равно требует экспоненциального времени.

Есть еще одна, более важная, теорема, которую нужно доказать для NP-полных про­блем: если любая из них принадлежит V, то весь класс AfP содержится в V. Но мы твердо верим, что в MV содержится много проблем, не принадлежащих V. Таким образом, до­казательство NP-полноты проблемы мы считаем равносильным доказательству того, что у нее нет алгоритма решения с полиномиальным временем, и поэтому она не имеет хо­рошего компьютерного решения.

Теорема 10.5. Если некоторая NP-полная проблема Р принадлежит V,ioV = MV.

Доказательство. Предположим, что Р одновременно и NP-полна, и принадлежит V. Тогда любой язык L из AfP полиномиально сводится к Р. Если Р принадлежит V, то и L принадлежит V (см. раздел 10.1.5). □

10.1.7. Упражнения к разделу 10.1

10.1.1. Каким будет ОДМВ для графа на рис 10.1, если вес его ребер изменить следую­щим образом:

а)   (*) вес 10 ребра (1,3) изменить на 25;

б)   изменить вес ребра (2, 4) на 16.

Альтернативные определения NP-полноты

Конечной целью изучения NP-полноты является теорема 10.5, т.е. поиск проблем Р, принадлежность которых классу V влечет равенство V = NV. Определение «NP- полноты», использованное здесь, часто называется полнотой по Карпу, поскольку оно впервые было использовано Р. Карпом в фундаментальной работе на данную те­му. Этому определению соответствует любая проблема, предположительно удовле­творяющая условиям теоремы 10.5.

Однако существуют другие, более широкие понятия NP-полноты, для которых теоре­ма 10.5 также справедлива. Например, С. Кук в своей первой работе, посвященной данному предмету, дал следующее определение «NP-полноты» проблемы Р. Пробле­му Р он назвал NP-полной, если, имея для проблемы Р оракул — механизм, который за единицу времени определяет, принадлежит ли данная цепочка Р, — можно распо­знать всякий язык из NP за полиномиальное время. Этот тип NP-полноты называют полнотой по Куку. В некотором смысле, полнота по Карпу есть частный случай этой полноты, когда оракулу задается лишь один вопрос. Однако полнота по Куку допус­кает отрицание ответа. Можно, например, задать оракулу некоторый вопрос, а в каче­стве ответа взять противоположное тому, что он ответит. Согласно определению пол­ноты по Куку, дополнение NP-полной проблемы также является NP-полной пробле­мой. Используя же более узкое определение полноты по Карпу, можно указать важное отличие NP-полных проблем от их дополнений. Это делается в разделе 11.1.

Каким будет гамильтонов цикл минимального веса для графа на рис. 10.1, если в него добавить ребро с весом 19, соединяющее узлы 1 и 4?

(*!) Предположим, что существует NP-полная проблема с детерминированным решением, занимающим время 0(ri^otl«). Заметим, что эта функция лежит меж­ду полиномами и экспонентами и не принадлежит ни одному из этих классов функций. Что можно сказать о времени, необходимом для решения произволь­ной проблемы из j\fPl

(!!) Рассмотрим графы, узлами которых являются узлы целочисленной решетки в «-мерном кубе со стороной длины т, т.е. векторы (z’_;, i₂, …, /„), где каждое г) находится в диапазоне от 1 до т (или от 0 до т — 1). Ребро между двумя узлами существует тогда и только тогда, когда они различаются на единицу ровно по одной координате. Например, вариант п = 2 и т = 2 представляет собой квадрат, я = 3им = 2 — куб, ая = 2ит = 3 — граф, изображенный на рис. 10.3. Некото­рые из этих графов имеют гамильтонов цикл, некоторые — нет. Например, квадрат имеет такой цикл. Куб — тоже, хотя это и не очевидно; примером явля­ется цикл (0, 0, 0), (0, 0, 1), (0, 1, 1), (0, 1, 0), (1, 1, 0), (1, 1, 1), (1, 0, 1), (1, 0, 0) и снова (0, 0, 0). Граф на рис. 10.3 гамильтонова цикла не имеет.

а)    Докажите, что граф на рис. 10.3 не имеет гамильтонова цикла. Указание. Нужно рассмотреть ситуацию, когда гипотетический гамильтонов цикл про­ходит через центральный узел. Откуда он может исходить и куда он может вести, не отсекая при этом части графа от гамильтонова цикла?

б)   Для каких значений пит гамильтонов цикл существует?

10.1.5. (!) Предположим, что у нас есть способ кодировки контекстно-свободных грамматик с помощью некоторого конечного алфавита. Рассмотрим следую­щие два языка.

1. L, = {(G, А, В) | G— (закодированная) КС-грамматика, А и В— (закоди­рованные) переменные G, причем множества терминальных цепочек, выво­димых из А и В, совпадают}.

2. L₂ = {(Gi, G₂) | G, и G₂ — (закодированные) КС-грамматики, и L(G,) = L(G₂)}. Выполните следующие задания:

а)   (*) покажите, что L, полиномиально сводится к L₂,

б)   покажите, что L₂ полиномиально сводится к L,;

в)   (*) что можно сказать об NP-полноте L, и 1₂ на основании а и 61

РиMP, как классы языков, обладают определенными свойствами замкнутости. Покажите, что класс V замкнут относительно следующих операций:

а)   обращение;

б)   (*) объединение;

в)   (*!) конкатенация;

г)   (!) замыкание (звездочка);

д)   обратный гомоморфизм;

е)   (*) дополнение.

Класс MP также замкнут относительно каждой из операций, перечисленных в упражнении 10.1.6, за (предполагаемым) исключением операции дополнения (пункт е). Замкнут ли класс MP относительно дополнения — неизвестно; этот вопрос обсуждается в разделе 11.1. Докажите, что MP замкнут относительно операций из пунктов а-д упражнения 10.1.6.

10.2. Первая NP-полная проблема

Теперь познакомимся с первой NP-полной проблемой— проблемой выполнимости булевых формул. Ее NP-полнота доказывается путем непосредственного сведения к ней языка любой недетерминированной МТ с полиномиальным временем.

10.2.1. Проблема выполнимости

Булевы формулы (выражения) строятся из следующих элементов.

Булевы переменные, принимающие значения 1 (истина) или 0 (ложь).

Бинарные операторы л и v, обозначающие логические связки И и ИЛИ двух формул.

Унарный оператор —который обозначает логическое отрицание.

Скобки для группирования операторов и операндов, если необходимо изменить по­рядок старшинства (приоритетов) операторов, принятый по умолчанию (вначале применяется затем л и, наконец, v).

Пример 10.6. Примером булевой формулы является хл—i(yvz). Подформула yvz имеет значение «истина», если истинна хотя бы одна из переменных у или z, и «ложь», если обе они ложны. Большая подформула —i(у v z) истинна лишь тогда, когда у v z ложно, т.е. когда обе переменные ложны. Если хотя бы одна из у или z истинна, то —i(y v z) ложно.

Рассмотрим, наконец, всю формулу. Поскольку она представляет собой логическое И двух подформул, то она истинна только тогда, когда истинны обе подформулы, т.е. 1л-п(у v z) истинна тогда и только тогда, когда х истинна, а у и z ложны. □

Выбрать подстановку (набор значений переменных) для данной булевой формулы Е — значит приписать значение «истина» или «ложь» каждой из переменных, фигури­рующих в Е. Значение формулы Е при данной подстановке Т, обозначаемое как Е(Т), — это результат вычисления Е, в которой каждая из ее переменных х заменена значением Т(х) («истина» или «ложь»), которое соответствует х в Т.

Формула Е истинна при подстановке Т, или подстановка Тудовлетворяет формуле Е, если Е(Т) = 1, т.е. данная подстановка Г делает формулу Е истинной. Булева форму­ла Е называется выполнимой, если существует хотя бы одна подстановка Т, для кото­рой Е истинна.

Пример 10.7. Формула хл—>(у v z) из примера 10.6 выполнима. Мы убедились, что эта формула истинна при подстановке Т, определенной равенствами Т(х) = 1, Т(у) = 0 и 7(2) = 0, поскольку принимает значение 1. Мы также заметили, что Т— единственная подстановка, удовлетворяющая этой формуле, поскольку для остальных семи комбина­ций значений трех переменных формула ложна (принимает значение 0).

В качестве еще одного примера рассмотрим формулу Е = х л (—х vy) л—у. Утвер­ждаем, что Е невыполнима. Поскольку переменных в ней всего две, то число возможных подстановок есть 2² = 4, так что нетрудно проверить их и убедиться, что при всех фор­мула Е принимает значение 0. Однако это можно обосновать и по-другому. Е истинна только тогда, когда все три члена, связанных л, истинны. Это значит, что х должно быть истинным (из-за первого члена), а у — ложным (из-за третьего члена). Но для такой под­становки значение среднего члена —сс v у ложно. Таким образом, значение Е не может быть истинным, и Е действительно невыполнима.

В одном из рассмотренных примеров у формулы была лишь одна удовлетворяющая подстановка, а в другом их вообще не было. Существует также множество примеров, в которых у формулы есть более одной удовлетворяющей подстановки. Например, рас­смотрим F = xv —у. Значение F есть 1 для трех следующих подстановок.

Ti(x) = 1; Tj(y) = 1.

Т₂(х) = 1; Т₂(у) = 0.

Т₃(х) = 0; Т₃(у) = 0.

F принимает значение 0 лишь для четвертой подстановки, где х = 0 и у= 1. Таким обра­зом, F выполнима. □

Проблема выполнимости состоит в следующем.

• Выяснить, выполнима ли данная булева формула.

Проблема выполнимости обычно обозначается как ВЫП. Если рассматривать ее как язык, то проблема ВЫП есть множество (закодированных) выполнимых булевых фор­мул. Цепочки, которые либо не образуют правильные коды булевых формул, либо явля­ются кодами невыполнимых булевых формул, не принадлежат ВЫП.

10.2.2. Представление экземпляров ВЫП

Символами в булевых формулах являются л, v, —левые и правые скобки, а также символы, представляющие переменные. Выполнимость формулы зависит не от имен переменных, а от того, являются ли два вхождения переменных одной и той же пере­менной или двумя разными. Таким образом, можно считать, что переменными явля­ются х_и х₂, …, хотя в примерах в качестве имен переменных по-прежнему используется не только х, но и имена вроде у или z. Считается также, что переменные переименованы так, что используются наименьшие из возможных индексов. Например, переменная х₅ не используется, если в той же формуле не использованы переменные xi~x₄.

Поскольку число переменных, встречающихся в булевых формулах, может быть бес­конечным, то мы сталкиваемся с уже знакомой проблемой разработки кода, имеющего фиксированный конечный алфавит, для представления формул с произвольным, сколь угодно большим, числом переменных. Только имея такой код, можно говорить о ВЫП как о «проблеме», т.е. языке с фиксированным алфавитом, состоящем из кодов выполни­мых булевых формул. Будем использовать следующий код.

Символы л, v, —1, ( и ) представляют самих себя.

Переменная х, представляется символом х с дописанной к нему последовательно­стью нулей и единиц — двоичной записью числа i.

Таким образом, алфавит проблемы/языка ВЫП содержит всего восемь символов. Все эк­земпляры ВЫП являются цепочками символов в этом фиксированном конечном алфавите.

Пример 10.8. Рассмотрим формулу х л -.(у v z) из примера 10.6. Первое, что нужно сделать для ее кодирования, — заменить переменные индексированными символами х. Поскольку переменных три, следует использовать X/, х₂ и х₃. Выбор х, для замены пере­менных х, у и z зависит от нас. Положим для определенности х = x_h у = х₂ и z = х₃. Тогда формула принимает вид х, л —,{х₂ v х₃), и ее кодом является х 1 л —i(x 10 v х 11). □

Отметим, что длина закодированной булевой формулы примерно равна числу пози­ций в этой формуле, если считать каждое вхождение переменной за 1. Разница возникает из-за того, что если формула имеет т позиций, то она может содержать 0(т) перемен­ных, и для кодирования каждой из них может понадобиться 0(log т) символов. Таким образом, формула длиной т позиций может иметь код длиной п = 0(т log ш) символов.

Однако разница между шиш logm, очевидно, ограничена полиномом. Поэтому, ес­ли нас интересует Лишь, можно ли решить проблему за время, полиномиально завися­щее от размера входных данных, то длину кода формулы и число позиций в ней разли­чать не обязательно.

10.2.3. NP-полнота проблемы ВЫП

Докажем «теорему Кука», утверждающую, что ВЫП NP-подна. Для доказательства, что некоторая проблема является NP-полной, сначала нужно показать, что она принад­лежит классу NV, а затем — что к ней сводится любой язык из jVP. Как правило, для до­казательства второй части к нашей проблеме полиномиально сводится какая-либо другая NP-полная проблема, а затем применяется теорема 10.5. Но пока у нас нет ни одной NP- полной проблемы, которую можно было бы свести к ВЫП. Поэтому нам остается только

сводить каждую без исключения проблему из MV к ВЫП. Теорема 10.9 (теорема Кука). Проблема ВЫП NP-полна.

Доказательство. В первой части доказывается, что ВЫП принадлежит MV- Сделать это довольно легко.

С помощью свойства недетерминированности НМТ для данной формулы Е угадыва­ем подстановку Т. Если код Е имеет длину п, то многоленточной НМТ для этого достаточно времени 0(п). Заметим, что у НМТ есть много возможностей выбора пе­реходов, и по окончании процесса угадывания она может иметь 2″ различных МО, где каждая ветка представляет угадывание отдельной подстановки.

Находим значение Е для подстановки Т. Если Е(Т) = 1, то допускаем. Отметим, что эта часть детерминирована. Тот факт, что другие ветки могут не приводить к допус- канию, никак не влияет на результат, поскольку НМТ допускает даже в том случае, если найдена всего одна удовлетворяющая подстановка.

Вычислить значение формулы с помощью многоленточной НМТ легко за время 0(п²). Таким образом, весь процесс распознавания ВЫП многоленточной НМТ занимает время 0(п²). Преобразование в одноленточную НМТ может возвести время в квадрат, так что одноленточной НМТ будет достаточно времени 0(п⁴).

Теперь нужно доказать трудную часть — что для произвольного языка L из MP суще­ствует полиномиальное сведение L к ВЫП. Можно предположить, что существует неко­торая одноленточная НМТ М и полином р(п), для которого М обрабатывает вход длиной п не более, чем за р(п) шагов вдоль любой ветки. Далее, ограничения, доказанные в тео­реме 8.12 для ДМТ, можно аналогично доказать и для НМТ. Поэтому можно предполо­жить, что М никогда не печатает пробела и никогда не сдвигает головку левее ее исход­ной позиции.

Итак, если М допускает вход w, и |vv| = п, то существует последовательность перехо­дов М со следующими свойствами.

ад — исходное МО М со входом w.

ао h «о/ Ь Н «ь гпек<р(п).

а_к — МО с допускающим состоянием.

4. Каждое а, не содержит пробелов (за исключением тех а„ которые заканчиваются со­стоянием и пробелом) и располагается вправо от исходной позиции головки — крайнего слева входного символа.

Стратегия построения формулы вкратце такова.

Каждое а, может быть записано как последовательность символов Х,оХц…Х_1р(п) дли­ной р(п) + 1. Один из них — состояние, а остальные р(п) — ленточные символы. Как обычно, предположим, что множества состояний и ленточных символов не пересе­каются, так что можно отличить, какое из Х_ц является состоянием, и указать, где на­ходится головка. Отметим, что нет надобности представлять символы, расположен­ные справа от первых р(п) символов на ленте, поскольку, если М гарантированно ос­танавливается, сделав не более р(п) переходов, то на переходы М эти символы справа не влияют.

Для описания последовательности МО в терминах булевых переменных введем пе­ременные y_ijA, которые представляют утверждения вида Хц = А. Здесь i и j— целые из интервала от 0 до р(п), а А — либо ленточный символ, либо состояние.

Условие того, что последовательность МО представляет допускание, записывается в виде булевой формулы, выполнимой тогда и только тогда, когда М допускает w в ре­зультате последовательности не более чем р(п) переходов. Удовлетворяющая под­становка «характеризует» МО, т.е. y_iJA истинна тогда и только тогда, когда Ху = А. Для гарантии того, что полиномиальное сведение L(M) к ВЫП корректно, эта фор­мула записывается так, чтобы отражать следующие свойства вычисления.

1. Правильный старт — исходное МО есть qo\v с последующими пробелами, п. Правильные переходы (т.е. согласующиеся с правилами МТ) — каждое последующее МО получается из предыдущего путем выполнения одно­го из возможных законных переходов М. iii. Правильный финиш — существует МО с допускающим состоянием.

Прежде, чем точно описать построение нашей булевой формулы, рассмотрим не­сколько деталей.

• Во-первых, по построению МО заканчивается там, где начинается бесконечный «хвост» из пробелов. Однако, имитируя вычисление за полиномиальное время, удобнее считать, что все МО имеют одну и ту же длину р(п) + 1. Поэтому в МО может присутствовать хвост из пробелов.
• Во-вторых, удобно считать, что все вычисления происходят в точности за р(п) переходов (и, следовательно, имеют р(п) + 1 МО), даже если допускание проис­ходит раньше. Следовательно, всякому МО с допускающим состоянием позволе­но быть собственным преемником, т.е., когда а содержит допускающее состоя­ние, разрешен «переход» а а. Таким образом, можно предполагать, что если

существует допускающее вычисление, то a_p(nJ имеет допускающее состояние, и это все, что нужно проверить в условии (iii).

На рис. 10.4 представлен общий вид полиномиального вычисления М. Строки соответст­вуют последовательности МО, а столбцы — это клетки на ленте, которые могут исполь­зоваться при вычислении. Заметим, что число ячеек на рис. 10.4 равно (р(п) + I)². Кроме того, число различных значений переменных, представляющих ячейки, конечно и зави­сит только от М; оно равно сумме числа состояний и числа ленточных символов М.

МО	0	1							p(ri)
Оо	Хоо	Xoi							Хо.р(пj
а,	Хю	Х„							Xl.p(n)
а,				Хц-1
				Xj+lj-l	Xi + lJ	Xi.lp,
ар(«)	Хр(п),0	ХР(П).’							Хр(п),р(п)

Рис. 10.4. Построение массива данных о последовательности МО

Приведем теперь алгоритм построения булевой формулы E_M:W по М и w. Общий вид {,« — S л N л F, где формулы S, N и F говорят о том, что М совершает правильный старт, переходы и финиш.

Правильный старт

Символ Х₀₀ должен быть начальным состоянием q₀ машины М, символы с Хщ по Х_0п — образовывать цепочку w (п — ее длина), а оставшиеся Х_0/ — быть пробелами В, т.е. если w = а₁а₂…а„, то

s ⁼ yooqo Л}>01а1 ^Уо2а2 ^Л «‘ ^лУопа„ ^лУо.п+1.В ^лУо,п+2,В ^л «»‘ ^лУо,р(п),В- Безусловно, по данным М nw можно записать S на второй ленте многоленточной МТ за время 0(р(п)).

Правильный финиш

Поскольку предполагается, что допускающее МО повторяется до бесконечности, то до­пускание М эквивалентно присутствию допускающего состояния в о._р(п). Напомним, что по предположению М является такой НМТ, которая, если допускает, то делает это в пределах р(п) шагов. Таким образом, F есть логическое ИЛИ формул Fj для j = 0, 1, …, р(п), где Fj утверждает, что X_p(n)J— допускающее состояние, т.е. Fj есть y_p(„_Ua, v y_P(„)j,_m v ■•• wу_рШаь где a_t, а₂,…, а_к — все допускающие состояния М. Тогда

F = F₀v F,v … vF_p(n).

Отметим, что в каждом из F, используется постоянное число символов, которое зависит от М, а не от длины п входа w. Поэтому F имеет длину 0{р(п)). Более важно то, что время, необходимое для записи F по данным коду М и цепочке w, полиномиально зависит от п. В действительности, формулу F можно записать на многоленточной МТ за время 0(р(п)).

Правильные переходы

Намного сложнее убедиться, что М правильно выполняет переходы. Формула N будет логическим И формул N„ где /’= 0, 1, …, р(п) — 1, и каждое N, строится так, чтобы а,., было одним из МО, в которые можно перейти из а) по правилам М. Чтобы понять, как следует записать N_h рассмотрим символ -Л», / , на рис. 10.4. Символ X, _{; /} всегда можно определить, зная:

а)   три символа над ним, т.е. X,j..i, Х_и и

б)    выбор перехода НМТ М, если один из этих символов есть состояние в а,. Запишем N, как логическое И формул А₀ v где j = 0, 1, …, р(п).

Формула Ау говорит о том, что:

а)   состояние МО а, находится в позиции j, т.е. X_v — состояние;

б)   если Ху — состояние и Хц-i — обозреваемый символ, то существует выбор такого перехода М, который преобразует последовательность символов Л’,, /Л’„Л’,,. / в X^ij-iXj-ijXi.ij^i. Заметим, что если Х_ц— допускающее со­стояние, то возможен только «выбор», при котором переход вообще не со­вершается, поэтому все последующие МО совпадают с первым, привед­шим к допусканию.

Формула By говорит о том, что:

а)   состояние МО а, достаточно далеко от Хц, так что оно не может влиять на Xj. ij (ни один из символов X_tJ ), X_t>, X_t/ , не является состоянием);

б)  X_lTlJ=X,j.

Формулу B,j записать легче, чем А,_г Пусть q,, q₂, …, q_m — состояния, a Z,, Z₂, …, Z_r — ленточные символы. Тогда

В„ = (y,J-l.Zl VДг-ЛЙ v ••• v у,j..,_iZr) л

(yij.zivyij,_z2v ■■■ чуцг_г)л

O/jw.z;                 v ••• vy,,jn,z_r) A

(yij.zi ^yi4.j,zi) v (yij,z2^y_j+ij_iZ2) v •■• v (y,j,z_r^y^i,j,zi)-

Первая, вторая и третья строчки в Вц соответственно выражают, что X,j /, Хц и Х_:/ , — ленточные символы. Последняя строчка выражает равенствоХ^ij-Х_ч\ в ней перечисля­ются все возможные ленточные символы Z, и говорится, что обе переменные — это либо Z;, либо Z₂ и т.д.

Существует два важных частных случая: j = 0 и j = p(ri). В первом нет переменных у,_{у /} а во втором — переменных Уц+ц. Однако нам известно, что головка никогда не сдвига­ется влево от своего исходного положения и что ей не хватит времени, чтобы сдвинуться более чем на р(п) клеток вправо от исходной. Поэтому из В,₀ и В,_р1п! можно выбросить некоторые члены. Выполните это упрощение самостоятельно.

Рассмотрим теперь формулы Ац. Эти формулы отражают все возможные связи между символами Ху-_1, Хц, X_itj+1, X,.-ij _h X, ij и X_i4j+j в прямоугольниках размером 2×3 из мас­сива (см. рис. 10.4). Подстановка символов в каждую из этих шести переменных является правильной, если:

а)  Хц есть состояние, а Х,_г1 и Хц _t -— ленточные символы;

б)   состоянием является только один из Xmj-i,XiHj и Д+лу+л

в)   существует переход М, объясняющий, как Xjj ;X,,X_IJ j превращается в X_l+lHX_i4 jX, -1 j+i-

Таким образом, для этих шести переменных существует лишь конечное число правиль­ных подстановок символов. Пусть Ац будет логическим ИЛИ членов, по одному для ка­ждого множества из шести переменных, образующего правильную подстановку.

Предположим, что переход М обусловлен тем, что S(q, А) содержит (р, С, L). Пусть D — некоторый ленточный символ М. Тогда Хц iX^X,^ , = DqA и X, , _{r l}X_l._{l /}X, i_J i = pDC — одна из правильных подстановок. Заметим, как эта подстановка отражает изменение МО, вызванное данным переходом М. Член, отражающий эту возможность, имеет вид

yi,j-i,D ^Ayij,q ^Ayij + 1.A ^Ayi + lj-l,p ^A У; HJ.D ^A + С- Если же 8(q, А) содержит (р, С, R), т.е. переход такой же, но головка сдвигается вправо, то со­ответствующая правильная подстановка— это X_}J iX_ltX,j / = DqA и X, ,Х, • i.jX, — ij ■ i — DC p. Соответствующий член имеет вид

УЦ-Ю ЛУцд ЛУу + м /\yhlj -1,D ^ЛУ1+1,/.С ^Ayi+l,j^I,p-

Формула Ац есть логическое ИЛИ всех правильных членов. В особых случаях, ко­гда j = 0 и j = р(п), нужно внести некоторые изменения, чтобы учесть отсутствие пере­менных уцх при j < 0 или j > р(п), как для Вц.

Наконец,

Mi = (4i₀ v В,о) л (А„ v Вц) л • • ■ л (Ai.p(n) ^v В_кр(п))

и

N = N₀aN,A ■■■ AN_p(„_h.

Несмотря на то что формулы A,j и Вц могут быть очень громоздкими (если М имеет много состояний и/или ленточных символов), их размер представляет собой константу и не зависит от длины входа w. Таким образом, длина N, есть 0(р(п)), а длина N — 0(р²(п)). Более важно то, что формулу N можно записать на ленту многоленточной МТ за время, пропорциональное ее длине, и это время полиномиально зависит от и — длины цепочки w.

Завершение доказательства теоремы Кука

Конструкция формулы

EM,w = S aNЛ F

была описана как функция, зависящая и от М, и от w, но в действительности только часть S — «правильный старт» — зависит от w, причем зависимость эта очень простая (w на­ходится на ленте начального МО). Остальные части, N и F, зависят только от М и п — длины входа w.

Итак, для всякой НМТ М с полиномиальным временем работы р(п) можно постро­ить алгоритм, который, получая на вход цепочку w длины п, выдает Е_Мн. Время рабо­ты такого алгоритма на многоленточной недетерминированной МТ есть 0(р²(п)), а многоленточную МТ, в свою очередь, можно преобразовать в одноленточную МТ со временем работы 0(р⁴(п)). Выходом данного алгоритма является булева формула Е_{м т} выполнимая тогда и только тогда, когда М допускает w в пределах первых р(п) пере­ходов. □

Рис. 10.5. Если ВЫП принадлежит Р, то принадлежность Рпроизвольного языка из А/Рможет быть доказана с помощью ДМТ указанного здесь вида

Для того чтобы подчеркнуть исключительную значимость теоремы Кука, рассмотрим применение к ней теоремы 10.5. Допустим, что экземпляры ВЫП могли бы распозна­ваться некоторой НМТ за полиномиальное время, скажем, д(п). Тогда всякий язык, до­пускаемый некоторой НМТ М за полиномиальное время р(п), допускался бы за полино­миальное время ДМТ, структура которой представлена на рис. 10.5. Вход w машины М преобразуется в булеву формулу E_MtU„ Затем эта формула подается на вход машины, рас­познающей ВЫП, и ответ, который она выдает для входа Е_м „,, будет ответом нашего ал­горитма для входа w.

Полиномиальный w—- преобразователь —► е для М

да

нет

10.2.4. Упражнения к разделу 10.2

Сколько удовлетворяющих подстановок имеют следующие формулы? Какие из них принадлежат ВЫП?

а)  (*) х л (у v —а) л (z v -1у);

б)  (х v у) л (—\(х v z) v (—za—ij-‘)).

(!) Рассмотрим граф G с четырьмя узлами: 1, 2, 3 и 4. Пусть хц, где 1 < i <j < 4, — булева переменная, интерпретируемая как высказывание: «существует ребро, соединяющее узлы i и /’. Всякий граф, содержащий эти четыре узла, можно представить некоторой подстановкой. Например, граф, изображенный на рис. 10.1, представляется подстановкой, где х_ы имеет зна­чение «ложь», а остальные переменные — «истина». Всякое свойство графа, касающееся только наличия или отсутствия тех или иных ребер, можно опи­сать с помощью булевой формулы, истинной тогда и только тогда, когда под­становка описывает граф с данным свойством. Запишите формулы для сле­дующих свойств:

а)  (*) G имеет гамильтонов цикл;

б)  G — связный;

в)   G содержит клику размера 3 (треугольник), т.е. множество из трех узлов, ка­ждые два из которых связаны ребром;

г)   G содержит хотя бы один изолированный узел (не имеющий ребер).

10.3. Ограниченная проблема выполнимости

Мы планируем доказать NP-полноту целого ряда проблем, таких как ПКОМ, упоми­наемая в разделе 10.1.4. Это можно сделать с помощью сведения проблемы ВЫП к каж­дой интересующей нас проблеме. Однако существует промежуточная проблема, назы­ваемая «ЗВЫП», которую намного проще свести к типичным проблемам, чем ВЫП. В проблеме ЗВЫП речь по-прежнему идет о выполнимости булевых формул (выражений), но эти выражения имеют строго определенный вид: они представляют собой логическое И «сумм», каждая из которых является логическим ИЛИ ровно трех переменных или их отрицаний.

В этом разделе вводится ряд важных терминов, относящихся к булевым формулам. Затем выполнимость формулы произвольного вида сводится к выполнимости выражения в форме, нормальной для проблемы ЗВЫП. Отметим, что всякая булева формула Е имеет эквивалентное выражение F в 3-КНФ, но размер F может экспоненциально зависеть от размера Е. Поэтому по сравнению с обычными для булевой алгебры преобразованиями полиномиальное сведение ВЫП к проблеме ЗВЫП должно быть более тонким. Всякую формулу Е из ВЫП нужно преобразовать в формулу F, находящуюся в 3-КНФ, но F не обязательно должна быть эквивалентной Е. Достаточно убедиться, что F выполнима то­гда и только тогда, когда выполнима Е.

10.3.1. Нормальные формы булевых выражений

Дадим три основных определения.

Литералом является либо переменная, либо отрицание переменной. Например, х или —у. Для краткости вместо литерала вида —у часто используется переменная с чертой сверху, у .

Дизъюнктом называется логическое ИЛИ одного или нескольких литералов, на­пример х, х v у, х v —у v z.

Говорят, что формула записана в конъюнктивной нормальной форме (КНФ) (здесь замысловатый термин «конъюнкция» обозначает логическое И), если пред­ставляет собой логическое И дизъюнктов.

Для придания записываемым выражениям большей компактности примем альтернатив­ные обозначения. Оператор v рассматривается как сложение, и вместо него используется оператор +, а а — как умножение, знак которого обычно опускается. Сомножители запи­сываются рядом, как при конкатенации в регулярных выражениях. Тогда дизъюнкт есте­ственно называть «суммой литералов», а КНФ — «произведением дизъюнктов (сумм)».

Пример 10.10. В сжатых обозначениях формула (х v -ту) а (—сс v z) имеет вид (х +у )(х + z). Она записана в КНФ, так как представляет собой логическое И (произ­ведение) сумм (х + у ) и (х + z).

Формула (х + у z )(х + у + z)( у + z ) не находится в КНФ. Она представляет собой ло­гическое И трех сумм (х+у z ), (х + у + z) и (у + z ), однако первая из них — не дизъ­юнкт, так как является суммой литерала и произведения двух литералов.

Формула xyz находится в КНФ. Напомним, что дизъюнкт может состоять и из одного- единственного литерала. Таким образом, наша формула представляет собой произведе­ние трех дизъюнктов: (х), (у) и (z). □

Говорят, что формула записана в k-конъюнктивной нормальной форме (&-КНФ), если представляет собой произведение дизъюнктов, каждый из которых является суммой ров­но к различных литералов. Например, формула (х + у )(у + z )(z + х) записана в 2-КНФ, так как каждый из ее дизъюнктов содержит ровно два литерала.

Все эти условия, накладываемые на булевы формулы, приводят к собственным про­блемам выполнимости формул, удовлетворяющих этим условиям. Таким образом, мы будем говорить о следующих проблемах.

Проблема ВКНФ: выполнима ли данная булева формула, записанная в КНФ?

Проблема &-ВЫП: выполнима ли данная булева формула, находящаяся в &-КНФ?

Обработка плохих входов

Каждая рассмотренная проблема (ВЫП, ВКНФ, ЗВЫП и т.д.) — это язык с фиксиро­ванным алфавитом из восьми символов, цепочки которого иногда можно интерпре­тировать как булевы формулы. Цепочка, которую нельзя интерпретировать как буле­ву формулу, не может принадлежать языку ВЫП. Аналогично, если рассматриваются формулы ограниченного вида, то цепочка, представляющая собой правильную булеву формулу, но не выражение требуемого вида, не может принадлежать данному языку. Например, алгоритм, решающий проблему ВКНФ, выдаст ответ «нет», если ему на вход подать булеву формулу, которая выполнима, но не находится в КНФ.

Мы увидим, что проблемы ВЫП, ЗВЫП и &-ВЫП при к> 3 NP-полны, но для проблем 1ВЫП и 2ВЫП существуют алгоритмы с линейным временем работы.

10.3.2. Преобразование формул в КНФ

Две булевы формулы^[2] называются эквивалентными, если имеют одно и то же значе­ние при любой подстановке. Если две формулы эквивалентны, то они либо обе выпол­нимы, либо обе невыполнимы. Поэтому, на первый взгляд, преобразование произволь­ных формул в эквивалентные формулы, записанные в КНФ, позволило бы. разработать метод полиномиального сведения ВЫП к ВКНФ. Это сведение свидетельствовало бы об NP-полноте ВКНФ.

Однако не все так просто. Мы действительно можем преобразовать всякую формулу в КНФ, но время этого преобразования может оказаться больше полиномиального. В ча­стности, при таком преобразовании длина формулы может вырасти экспоненциально, и тогда, безусловно, время порождения выхода также экспоненциально возрастет.

К счастью, приведение произвольной булевой формулы к КНФ — это лишь один из возможных способов сведения ВЫП к ВКНФ, и доказательства, таким образом, NP-пол­ноты ВКНФ. В действительности достаточно взять экземпляр ВЫП Е и преобразовать его в экземпляр ВКНФ F, выполнимый тогда и только тогда, когда выполним Е. Форму­лы Е и F могут быть неэквивалентными. Не требуется даже, чтобы множества перемен­ных Е и F совпадали; множество переменных F будет, как правило, надмножеством множества переменных Е.

Сведение ВЫП к ВКНФ состоит из двух частей. На первом этапе все отрицания «спускаются» вниз по дереву выражения, так что в формуле присутствуют только отрицания переменных. Булева формула превращается в логическое И и ИЛИ литералов. Это преобра­зование дает формулу, эквивалентную исходной, и занимает время, как максимум, квадратич­ное относительно длины этой формулы. При реализации на обычном компьютере с тщатель­но выбранной структурой данных это преобразование требует линейного времени.

Второй этап— переписать формулу, которая представляет собой логическое И и ИЛИ литералов, в виде произведения дизъюнктов, т.е. привести ее к КНФ. Введение но­вых переменных позволяет провести это преобразование за время, полиномиально зави­сящее от размера исходной формулы. Новая формула F, вообще говоря, не будет эквива­лентна старой формуле Е. Но F будет выполнима тогда и только тогда, когда выполнима Е. Точнее, если Т— некоторая подстановка, для которой Е истинна, то существует рас­ширение Т, скажем S, для которого истинна F. Расширение S подстановки Т— это под­становка, приписывающая переменным Т те же значения, что и Т, и, кроме того, в ней есть переменные, которых не было в Т.

На первом этапе нужно спустить операторы —i ниже операторов л и v. Для этого ис­пользуются следующие правила.

—i(E л F) => —<(Е) v —1 (F). Это правило — один из законов Де Моргана — позволяет спустить оператор под оператор д. Отметим, что в виде побочного эффекта л ме­няется на v.

-1 (Е v F) => -.(£) л -1 (F). Другой «закон Де Моргана» позволяет спустить —. под опе­ратор v, изменяемый на л.

—i(-i(£)) => Е. Этот закон двойного отрицания уничтожает пару операторов —при­меняемых к одной формуле.

Пример 10.11. Рассмотрим формулу Е = —1((—.(х + х + у)). Заметим, что в ней пе­ремешаны оба используемых обозначения. Оператор —i использован явно, когда форму­ла, отрицание которой берется, состоит более чем из одной переменной. На рис. 10.6 по­казано, как формула переписывается шаг за шагом до тех пор, пока отрицания —i не ста­нут составляющими литералов.

Формула	Правило
	Начало
	(О
х+у + ^,(х+у)	(3)
х + у + (-л(х))у	(2)
х+у+ху	(3)

Рис. 10.6. Спуск отрицаний вниз по дереву формулы так, чтобы они встречались только в литералах

Заключительная формула эквивалентна исходной и состоит из логических связок И и ИЛИ литералов. Ее можно упростить до формулы х + у, но это упрощение несуществен­но для нашего утверждения о том, что формулу можно переписать так, чтобы оператор —> присутствовал только в литералах. □

Теорема 10.12. Всякая булева формула Е эквивалентна формуле F, в которой отрица­ния присутствуют только в литералах, т.е. применяются непосредственно к переменным. Более того, длина F линейно зависит от количества символов в Е, и F можно построить по Е за полиномиальное время.

Доказательство. Используем индукцию по числу операторов (л, v и —i) в Е. Пока­жем, что существует эквивалентная формула F, в которой —i присутствует только в ли­тералах. Кроме того, если Е содержит п > 1 операторов, то F содержит не более 2п — 1 операторов.

Поскольку формуле F достаточно одной пары скобок для каждого оператора, а число переменных в ней не может превышать числа операторов больше, чем на еди­ницу, то приходим к выводу, что длина F линейно пропорциональна длине Е. Более важно, как мы увидим, что время построения F пропорционально ее длине и, следова­тельно, — длине Е.

Базис. Если Е содержит один оператор, то она должна иметь вид -ее, xwy или х л у, где х и у — переменные. В каждом из этих случаев формула уже имеет требуемый вид, поэтому F— Е. Отметим, что, поскольку и £, и F содержат по одному оператору, то со­отношение «число операторов в F не превышает числа операторов в Е, умноженного на два, минус один» выполняется.

Индукция. Предположим, что утверждение справедливо для всех формул, число операторов в которых меньше, чем в Е. Если верхний оператор в Е — не то формула должна иметь вид v Е₂ или Е₁ л Е₂. В любом из этих случаев гипотеза индукции при­менима к формулам Ei и Е_ъ и согласно ей существуют эквивалентные формулы — F, и F₂, соответственно, — в которых —i встречается только в литералах. Тогда F = F/vF₂ или F= (Fi) л (F₂) служат подходящими эквивалентами для Е. Пусть E_t и Е₂ содержат соответственно а и Ь операторов. Тогда Е содержит а + Ь + 1 операторов. Согласно гипоте­зе индукции Fi и F₂ содержат соответственно 2а — i и 2Ь — 1 операторов. Таким образом, F содержит не более, чем 2а + 26- 1 операторов, что не превосходит 2(a + b+ 1)- 1, или числа операторов в Е, умноженного на два, минус 1.

Рассмотрим теперь случай, когда Е имеет вид —,Е/. В зависимости от верхнего опера­тора в формуле Е/ возможны три варианта. Заметим, что £_; содержит хотя бы один опе­ратор, иначе Е — формула из базиса.

1. Е/ = -£₂— Тогда согласно закону двойного отрицания формула £=-i-i(£₂) эквива­лентна Е₂. Гипотеза индукции применима, так как в Е₂ содержится меньше операто­ров, чем в Е. Можно найти формулу F, эквивалентную Е₂, в которой отрицания встречаются только в литералах. Формула F годится и для Е. Поскольку число опе­раторов в F не превышает числа операторов в Е₂, умноженного на два, минус 1, то оно, конечно же, не превышает числа операторов в Е, умноженного на два, минус 1.

£/ = E₂v E₃. Согласно закону Де Моргана формула Е = -,(Е₂ v Е₃) эквивалентна (—{Е₂)) л (—1 (Е₃)). Обе формулы —.(Е₂) и —i(Е₃) содержат меньше операторов, чем Е. Поэтому согласно гипотезе индукции существуют эквивалентные им формулы F₂ и F₃, в которых отрицания встречаются только в литералах. Тогда эквивалентом Е служит формула F = (F₂) л (F₃). Кроме того, мы утверждаем, что число операторов в F не слишком велико. Пусть Е₂ и Е₃ содержат соответственно а и Ь операторов. То­гда в Е содержится а + Ь + 2 операторов. Поскольку в формулах -i(Е₂) и -i(Е₃) соот­ветственно а + 1 и b + 1 операторов, и формулы F₂ и F₃ построены по этим формулам, то согласно гипотезе индукции в F₂ и F₃ не больше, чем 2(а + 1) — 1 и 2(6 + 1) — 1 опе­раторов соответственно. Таким образом, F содержит не более 2а + 2Ь + 3 операто­ров, а это и есть число операторов в Е, умноженное на два, минус 1.

Е/ = Е₂ л Е₃. Обоснование этой части, использующее второй закон Де Моргана, ана­логично пункту 2.

□

Описания алгоритмов

Формально время работы алгоритма сведения есть время, необходимое для выполне­ния его на одноленточной машине Тьюринга, однако такие алгоритмы слишком сложны. Мы знаем, что множества проблем, которые можно решить за полиномиаль­ное время на обычных компьютерах, многоленточных и одноленточных МТ, совпа­дают, хотя степени полиномов при этом могут различаться. Таким образом, описывая некоторые по-настоящему сложные алгоритмы, требующие сведения одной NP-пол­ной проблемы к другой, примем соглашение, что время сведения будет ограничено временем работы его эффективной реализации на обычном компьютере. Это избавит нас от подробностей обработки лент и позволит выделить по-настоящему важные ал­горитмические идеи.

10.3.3. NP-полнота проблемы ВКНФ

Теперь нам необходимо привести к КНФ формулу Е, которая состоит из логических И и ИЛИ литералов. Как уже упоминалось, чтобы за полиномиальное время создать по Е формулу F, выполнимую тогда и только тогда, когда выполнима Е, нужно отказаться от преобразования, сохраняющего эквивалентность формул, и ввести в F новые перемен­ные, отсутствующие в Е. Используем этот прием в доказательстве теоремы об NP-полноте проблемы ВКНФ, а затем приведем пример его применения.

Теорема 10.13. Проблема ВКНФ NP-полна.

Доказательство. Покажем, как свести ВЫП к ВКНФ за полиномиальное время. Вна­чале с помощью метода, описанного в теореме 10.12, преобразуем данный экземпляр ВЫП в формулу Е, содержащую —> только в литералах. Затем покажем, как за полиноми­альное время преобразовать Е в КНФ-формулу F, выполнимую тогда и только тогда, ко­гда выполнима Е. Формула F строится индуктивно по длине Е, а ее конкретные свойст­ва— это даже больше, чем нам нужно. Точнее, индукцией по числу вхождений символов в Е («длине») докажем следующее утверждение.

• Пусть Е — булева формула длины п, в которой —i встречается только в литералах.

Тогда существуют константа с и формула F, удовлетворяющие утверждениям:

а)  F находится в КНФ, и содержит не более п дизъюнктов;

б)  F можно построить по Е за время, не превышающее с|£|²;

в)   подстановка Г для Е делает Е истинной тогда и только тогда, когда сущест­вует расширение S подстановки Т, удовлетворяющее формуле F.

Базис. Если Е состоит из одного или двух символов, то оно — литерал. Литерал яв­ляется дизъюнктом, поэтому Е уже находится в КНФ.

Индукция. Предположим, что всякую формулу, более короткую, чем Е, можно преоб­разовать в произведение дизъюнктов, и для формулы длиной п это преобразование занима­ет время не более сп². В зависимости от верхнего оператора Е возможны два варианта.

Вариант 1. Е= Е, л Е₂. Согласно гипотезе индукции существуют формулы Fi и F₂, которые выводятся из E_t и Е₂, соответственно, и находятся в КНФ. Все подстановки, удовлетворяющие E_h и только они, могут быть расширены до подстановок, удовлетво­ряющих F,. То же самое верно для Е₂ и F₂. Не теряя общности, можно предполагать, что переменные в F/ и F₂ различны, за исключением переменных, присутствующих в Е, т.е. вводимые в Fi и/или F₂ переменные выбираются различными.

Рассмотрим F- Fi a F₂. Очевидно, что формула F, л F₂ находится в КНФ, если в КНФ находятся F, и F₂. Нам нужно показать, что подстановку Т для формулы Е можно расши­рить до подстановки, удовлетворяющей F, тогда и только тогда, когда Г удовлетворяет Е.

(Достаточность) Пусть Т удовлетворяет Е. Пусть Tt и Т₂ — сужения подстановки Т, применяемые только к переменным формул Е/ и Е₂, соответственно. Тогда согласно ин­дуктивной гипотезе Ti и Т₂ могут быть расширены до подстановок S/ и S₂, удовлетво­ряющих Fj и F₂, соответственно. Пусть S— подстановка, согласованная с Si и S₂, т.е. приписывает переменным те же значения, что Si и S₂. Заметим, что лишь переменные из Е присутствуют и в F_h и в F₂, поэтому подстановки S/ и S₂ согласованы на переменных, на которых обе они определены, и построить S всегда возможно. Но тогда S есть расши­рение Т, удовлетворяющее F.

(Необходимость) Наоборот, пусть подстановка Т имеет расширение S, удовлетво­ряющее F. Пусть Т, (Т₂) — сужение Т на переменные Е, (Е₂). Сужение S на переменные Fi (F₂) обозначим через S, (S₂). Тогда S, — это расширение Т,, a S₂ — расширение Т₂. Поскольку F есть логическое И формул F, и F₂, Si должна удовлетворять формуле F_h а S₂— формуле F₂. Согласно гипотезе индукции Т, (Т₂) должна удовлетворять Е, (Е₂). По­этому Гудовлетворяет Е.

Вариант 2. Е = Ej v Е₂. Как и в предыдущем случае, обращаемся к индуктивной гипо­тезе, утверждающей, что существуют формулы Fi и F₂, которые обладают следующими свойствами.

Подстановка для формулы Е₁ (Е₂) удовлетворяет Е, (Е₂) тогда и только тогда, когда она может быть расширена до подстановки, удовлетворяющей формуле Fi (F₂).

Переменные в формулах Fi и F₂ различны, за исключением присутствующих в Е.

Формулы Fi и F₂ находятся в КНФ.

Для того чтобы построить искомую формулу F, мы не можем просто объединить F_; и F₂ логическим ИЛИ, так как полученная в результате формула не будет находиться в КНФ. Однако можно использовать более сложную конструкцию, которая учитывает, что важно сохранить выполнимость формул, а не их эквивалентность. Предположим, что Ei ⁼ gi a g₂ л … a g_p и F₂ = hi a h₂ а … л h_q, где символы g и h обозначают дизъюнкты. Введем новую переменную у и определим

О + g/) а(у+ g₂) А … A(y + g_p)A(j? +h,)A(y + h₂) А … а(у + h_q).

Мы должны доказать, что подстановка Г удовлетворяет Е тогда и только тогда, когда Т может быть расширена до подстановки S, удовлетворяющей F.

(Необходимость) Пусть подстановка Г удовлетворяет Е. Как и в варианте 1, обозна­чим через ТI (Т₂) сужение Т на переменные Е/ (Е₂). Поскольку Е= E,w Е₂, то Г удовле­творяет Ei или Е₂. Предположим, что £/ истинна при Т. Тогда подстановку Т,, представ­ляющую собой сужение Т на переменные E_h можно расширить до подстановки S7, для которой истинна F_h Расширение S подстановки Т, для которого истинна определенная выше формула F, построим следующим образом.

S(x) = S/(x) для всех переменных х m F,.

S(y) = 0. Этим выбором всем дизъюнктам F, полученным из F₂, придается значение «истина».

Для всех переменных х из F₂, отсутствующих в F_h S(x) может принимать значения 0 или 1 произвольно.^[3]

По правилу 1 подстановка S делает истинными все дизъюнкты, полученные из дизъюнк­тов g, а по правилу 2 — все дизъюнкты, полученные из дизъюнктов h. Поэтому подста­новка S удовлетворяет формуле F.

Если подстановка Т не удовлетворяет Е,, но удовлетворяет Е₂, то расширение строит­ся аналогично, за исключением того, что S(y) = 1 в правиле 2. Подстановка S(x) согласу­ется с S₂(x) на переменных, на которых определена S₂(x), а значения переменных, при­сутствующих только в Si, в подстановке S произвольны. Приходим к выводу, что и в этом случае F истинна при S.

(Достаточность) Предположим, что подстановка Г для Е расширена до подстановки S для F,hF истинна при S. В зависимости от значения переменной у возможны два слу­чая. Пусть S(y) = 0. Тогда все дизъюнкты, полученные из дизъюнктов И, истинны. Одна­ко у ложно в дизъюнктах вида (у + gi), получаемых из g,. Это значит, что S придает зна­чение «истина» самим g„ так что F, истинна при подстановке S.

Более строго, пусть Si — сужение S на переменные F_h Тогда Fi истинна при S,. По­скольку S1 — это расширение подстановки Т,, являющейся сужением Т на переменные Ei, то согласно гипотезе индукции Е, должна быть истинной при подстановке T_h Но F_t истинна при T_h поэтому формула Е, представляющая собой Е, v Е₂, должна быть истин­ной при Т.

Остается рассмотреть случай S(y) = 1, аналогичный предыдущему, и это предоставля­ется читателю. Итак, Е истинна при Т, если только F истинна при S.

Теперь нужно показать, что время, необходимое для построения F по Е, не превыша­ет квадрата п — длины Е. Независимо от возможного случая, обе процедуры — разбие­ние Е на Ei и Е₂ и построение формулы F по F, и F₂ — занимают время, линейно зави­сящее от размера Е. Пусть dn — верхняя граница времени, необходимого для построения формул Ei и Е₂ по Е, вместе со временем, затрачиваемым на построение формулы F по F1 и F₂, в любом из вариантов 1 и 2. Тогда Т(п) — время, необходимое для построения F по Е, длина которой п, описывается следующим рекуррентным соотношением.

7(1) = Т(2) < е, где е — некоторая константа.

Т(п) <dn + cmax_{0 Kn ;} (7Т(/) + Т{п — 1 — 0) для п > 3. Константу с еще предстоит определить так, чтобы Т(п) < сп². Базисное правило для 7(1) и 7(2) говорит о том, что если Е— одиночный символ или пара символов, то рекурсия не нужна, поскольку Е может быть только одиночным литералом, и весь процесс зани­мает некоторое время е. В рекурсивном правиле используется тот факт, что Е составлена из подформул Б, и Е₂, связанных оператором а или v, и, если Е, имеет длину i, то Е₂ имеет длину n — i— 1. Более того, весь процесс построения F по Е состоит из двух про­стых шагов — замены Е формулами Е, и Е₂ и замены Fi и F₂ формулой F, — которые, как мы знаем, занимают время, не превышающее dn, плюс два рекурсивных преобразо­вания Е) в Fi и Е₂ в F₂.

Докажем индукцией по п, что существует такая константа с, при которой Т(п) < сп² для всех п> 0.

Базис. Для п = 1 нам нужно просто выбрать с не меньше, чем е.

Индукция. Допустим, что утверждение справедливо для длин, которые меньше п. Тогда T(i) < ci² и Т(п — i — 1) < с(п — i — 1 )². Таким образом,

ДО + Г(п -i-\)<n²— 2i(n — i) — 2(п -0+1                                          (10-0

Поскольку п> 3 и 0 < i < и — 1, то 2i(n — t) не меньше п, а 2(n-i) не меньше 2. Поэтому для любого i в допустимых пределах правая часть (10.1) меньше п²-п. Тогда T(ri) <dn + сп² — сп согласно рекурсивному правилу из определения Т(п). Выбирая с > d, можно сделать вывод, что неравенство Т(п) < сп² справедливо для п, и завершить индукцию. Таким образом, конструкция F из Е занимает время 0(п²). □

Пример 10.14. Покажем, как конструкция теоремы 10.13 применяется к простой формуле Е = ху + х (у + z). Разбор данной формулы представлен на рис. 10.7. К каждому узлу припи­сано выражение в КНФ, которое построено по выражению, представленному этим узлом.

( и + х) (и +7)Сй+Т) (ТТ + v +у) (V +»v + z)

Рис. 10.7. Приведение булевой формулы к КНФ

Листья соответствуют литералам, и КНФ для каждого литерала — это дизъюнкт, со­стоящий из одного такого литерала. Например, лист с меткой у связан с КНФ (у). Скобки тут не обязательны, но мы ставим их в КНФ, подчеркивая, что речь идет о про­изведении дизъюнктов.

Для узла с меткой И соответствующая КНФ получается как произведение (И) всех дизъюнктов двух подформул. Поэтому, например, с узлом, соответствующим выраже­нию x(y + z), связана КНФ в виде произведения одного дизъюнкта (х), соответствую­щего х , и двух дизъюнктов (v + )’Х v + z), соответствующих у + z.^[4]

Для узла с меткой ИЛИ нужно ввести новую переменную. Добавляем ее во все дизъ­юнкты левого операнда и ее отрицание во все дизъюнкты правого операнда. Рассмотрим, например, корневой узел на рис. 10.7. Он представляет собой логическое ИЛИ формул ху и x(y + z), для которых соответствующие КНФ были определены как (х)(у) и (x )(v + y)( v + z), соответственно. Вводим новую переменную и, добавляя ее в дизъюнк­ты первой группы, а ее отрицание — в дизъюнкты второй группы. В результате получа­ем формулу

F = (и + х)(и + у )(й + х )(й + v + у)(й + v + z)

В теореме 10.13 говорится, что всякую подстановку Т, удовлетворяющую Е, можно расширить до подстановки S, удовлетворяющей F. Например, Е истинна при подстанов­ке Т(х) = 0, Т(у) = 1 и Т(~) = 1. Можно расширить Т до подстановки S, добавляя значения S(u) = 1 и S(v) = 0 к требуемым S(x) = 0, S(y) = 1 и S(z) = 1, которые берутся из Т. Нетруд­но убедиться, что F истинна при S.

Заметим, что, выбирая S, мы были вынуждены выбрать S(u) = 1, так как подстановка Г делает истинной только вторую часть Е— x(y + z). Поэтому для того, чтобы истин­ными были дизъюнкты (и + х)(и + у ) из первой части Е, необходимо S(u) = 1. Но значе­ние для v можно выбрать любым, так как в соответствии с Г в подформуле у + z истинны оба операнда логического ИЛИ. □

10.3.4. NP-поднота проблемы 3-выполнимости

Покажем, что проблема выполнимости NP-полна даже для более узкого класса буле­вых формул. Напомним, что проблема ЗВЫП (3-выполнимости) состоит в следующем.

• Дана булева формула Е, представляющая собой произведение дизъюнктов, каж­дый из которых есть сумма трех различных литералов. Выполнима ли Е1 Несмотря на то что формулы вида 3-КНФ — лишь небольшая часть КНФ-формул, их сложности достаточно, чтобы проверка их выполнимости была NP-полной проблемой. Это показывает следующая теорема.

Теорема 10.15. Проблема ЗВЫП NP-полна.

Доказательство. Очевидно, что ЗВЫП принадлежит MP, поскольку ВЫП принадле­жит NV. Для доказательства NP-полноты сведем ВКНФ к ЗВЫП следующим образом. В данной КНФ Е = е_; л е₂ л •■• л е_к каждый дизъюнкт е, заменяется, как описано ниже, и создается новая формула F. Время, необходимое для построения F, линейно зависит от длины Е, и, как мы увидим, подстановка удовлетворяет формуле Е тогда и только тогда, когда ее можно расширить до подстановки, удовлетворяющей F.

1. Если е, — одиночный литерал, скажем, (х)^[5], то вводятся две новые переменные и и v, и (х) заменяется произведением четырех дизъюнктов

(х + и + v)(x + и + v )(х + й + v)(x + й + v ).

Поскольку здесь присутствуют все возможные комбинации из и и v, то все четыре дизъюнкта истинны только тогда, когда х истинна. Таким образом, все подстановки, удовлетворяющие Е, и только они, могут быть расширены до подстановки, удовле­творяющей F.

2. Предположим, что е, есть сумма двух литералов — (х + >•)• Вводится новая перемен­ная z, и е, заменяется произведением двух дизъюнктов (х + у + z)(x + у+z). Как и в случае 1, оба дизъюнкта истинны одновременно только тогда, когда истинна (х + у).

• Если дизъюнкт е, есть сумма трех литералов, то он уже имеет вид, требуемый 3-КНФ, и остается в. создаваемой формуле
• Предположим, что e_t = (xj + х₂ + ■■■ + х_т) при некотором т> 4. Вводятся новые пе­ременные у/,у₂, заменяется произведением дизъюнктов

(х/ + Х₂ + уд(х₃ + у I + у₂){х₄ + у 2 + Уз)-■ ■

(*т 2+ У т 4+Ут -з)(*т 1 +             У т — 3 )■                                             (10.2)

Подстановка Т, удовлетворяющая Е, должна делать истинным хотя бы один из литера­лов в е„ скажем х₍ (напомним, что х, может быть либо переменной, либо ее отрицани­ем). Тогда, если придать переменным y_h у₂, …, y_t, значение «ложь», a y_h y_ri, …, y_m з— «истина», то все дизъюнкты в (10.2) будут истинными. Таким образом, Т можно расширить до подстановки, удовлетворяющей всем этим дизъюнктам. На­оборот, если при подстановке Т все х имеют значение «ложь», то Т невозможно рас­ширить так, чтобы формула (10.2) была истинной. Причина в том, что дизъюнктов m — 2, а каждый у, которых всего т- 3, может сделать истинным лишь один дизъ­юнкт, независимо от того, имеет ли он значение «истина» или «ложь».

Таким образом, мы показали, как свести любой экземпляр Е проблемы ВКНФ к эк­земпляру F проблемы ЗВЫП, выполнимому тогда и только тогда, когда выполнима фор­мула Е. Построение, очевидно, требует времени, которое линейно зависит от длины Е, так как ни в одном из рассмотренных выше четырех случаев длина дизъюнкта не увели­чивается более, чем в 32/3 раза (соотношение числа символов в случае 1). Кроме того, символы, необходимые для построения формулы F, легко найти за время, пропорцио­нальное числу этих символов. Поскольку проблема ВКНФ NP-полна, то и проблема ЗВЫП также NP-полна. □

10.3.5. Упражнения к разделу 10.3 10.3.1. Приведите следующие формулы к 3-КНФ:

а)   (*)xy + xz;

б)   wxyz + и + v;

в)   wxy + х uv.

Проблема 4П-ВЫП определяется следующим образом: по данной булевой фор­муле Е выяснить, есть ли у нее хотя бы четыре удовлетворяющие подстановки. Покажите, что проблема 4П-ВЫП NP-полна.

В этом упражнении определяется семейство 3-КНФ-формул. Формула Е„ имеет п переменных x_h х₂, -.., х„. Для всякого множества из трех различных целых чи­сел от 1 до и формула Е„ содержит дизъюнкты (х, + х₂ + х₃) и (х /+ х₂ + х ₃). Выполнима ли Е„ для:

а)   (*!)« = 4?

б)   (!!)« = 5?

(!) Постройте алгоритм с полиномиальным временем работы для решения проблемы 2ВЫП (2-выполнимости), т.е. проблемы выполнимости булевой формулы в КНФ, каждый дизъюнкт которой содержит ровно два литерала. Указание. Если один из двух литералов в дизъюнкте ложен, то второй обяза­тельно истинен. Сделайте вначале предположение относительно истинности одной из переменных, а затем постарайтесь извлечь все возможные следствия для оставшихся переменных.

10.4. Еще несколько NP-полных проблем

Приведем несколько примеров того, как с помощью одной NP-полной проблемы можно доказать NP-полноту целого ряда других. Этот процесс получения новых NP- полных проблем имеет два важных следствия.

Обнаружив новую NP-полную проблему, мы не получаем практически никаких шансов на отыскание эффективного алгоритма ее решения. Мы стремимся найти эвристики, частные решения, аппроксимации, применяем какие-либо иные мето­ды, лишь бы избежать решения «в лоб». Более того, мы можем делать все это, будучи уверенными, что не просто «не замечаем метод».

Всякое добавление новой проблемы Р в список NP-полных проблем дает еще одно подтверждение гипотезы, что все они требуют экспоненциального време­ни. Усилия, затраченные на поиски полиномиального алгоритма решения про­блемы Р, мы, сами того не зная, посвятили обоснованию равенства V — MV. Именно безуспешные попытки многих первоклассных математиков и других ученых доказать нечто эквивалентное утверждению V = MV в конечном счете убеждают в том, что это равенство невероятно и, наоборот, все NP-полные проблемы требуют экспоненциального времени.

В этом разделе мы встретим несколько NP-полных проблем, связанных с графами. Эти проблемы чаще других используются при решении практических вопросов. Мы по­говорим о проблеме коммивояжера (ПКОМ), с которой уже встречались в разделе 10.1.4. Покажем, что более простая, но также важная версия этой проблемы, называемая про­блемой гамильтонова цикла (ГЦ), NP-полна. Тем самым покажем, что NP-полной явля­ется и более общая проблема ПКОМ. Представим несколько проблем, касающихся «покрытия» графов, таких, как «проблема узельного покрытия». В ней требуется оты­скать наименьшее множество узлов, «покрывающих» все ребра так, чтобы хотя бы один конец каждого ребра принадлежал выбранному множеству.

Описание NP-полных проблем

Вводя новую NP-полную проблему, будем использовать следующую стилизованную форму ее определения.

Название проблемы и, как правило, его аббревиатура, например, ВЫП или ПКОМ.

Вход проблемы: что и каким образом представляют входные данные.

Искомый выход: при каких условиях выходом будет «да».

Проблема, сведение которой к данной доказывает NP-полноту последней.

Пример 10.16. Вот как могут выглядеть описание проблемы 3-выполнимости и дока­зательство ее NP-полноты.

Проблема. Выполнимость формул, находящихся в 3-КНФ (ЗВЫП). Вход. Булева формула в 3-КНФ.

Выход. Ответ «да» тогда и только тогда, когда формула выполнима. Проблема, сводящаяся к данной. ВКНФ. □

Проблема независимого множества

Пусть G — неориентированный граф. Подмножество / узлов G называется независи­мым множеством, если никакие два узла из I не соединены между собой ребром из G. Независимое множество является максимальным, если оно не меньше (содержит не меньше узлов), чем любое независимое множество этого графа.

Пример 10.17. Для графа, изображенного на рис. 10.1 (см. раздел 10.1.2), максималь­ным независимым множеством является {1,4}. Это единственное множество размера два, которое является независимым, поскольку для любых других двух узлов существует соединяющее их ребро. Таким образом, никакое множество размера три и более не явля­ется независимым, например, множество {1, 2, 4} (есть ребро между узлами 1 и 2). Итак, {1,4} — максимальное независимое множество, причем единственное для данного гра­фа, хотя граф может иметь много максимальных независимых множеств. Например, множество {1} также независимо для данного графа, но не максимально. □

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

Проблема. Независимое множество (НМ).

Вход. Граф G и нижняя граница к, значение которой заключено между 1 и числом узлов G.

Выход. Ответ «да» тогда и только тогда, когда G имеет независимое множество из к узлов.

Проблема, сводящаяся к данной. Проблема ЗВЫП. Мы должны, как и пообещали, доказать NP-полноту проблемы НМ, сведя к ней пробле­му ЗВЫП.

Теорема 10.18. Проблема независимого множества NP-полна.

Доказательство. Легко видеть, что проблема НМ принадлежит классу MV. Для дан­ного графа G нужно угадать набор из к его узлов и проверить их независимость.

Теперь опишем сведение ЗВЫП к НМ. Пусть Е = (е/)(е₂) •■• (е_т) — формула в 3-КНФ. По Е строится граф G, содержащий 3т узлов, которые обозначим как [г, j], где 1< i<m, а у = 1,2 или 3. Узел [г, у] представляет j-й литерал в дизъюнкте е,. На рис.10.8 приведен пример графа G, построенного по 3-КНФ

(*/+ Х2 + J| + Х2 + Xj)( х2 + Xj+XjX 3?з+ Х4+ х} ). Рис. 10.8. Построение независимого множества по выполнимой булевой формуле, находящейся в 3-КНФ

Дизъюнкты формулы представлены столбцами. Поясним вкратце, почему узлы имеют именно такой вид.

«Фокус» построения G состоит в том, чтобы каждое независимое множество из т уз­лов представляло один из способов выполнить формулу Е. Ключевых идей тут две.

Мы хотим гарантировать, что можно выбрать только один узел, соответствующий данному дизъюнкту. Для этого помещаем ребра между каждой парой узлов из од­ного столбца, т.е. создаем ребра ([/, 1], [/, 2]), ([/’, 1], [i, 3]) и ([/, 2], [г, 3]) для всех i (см. рис. 10.8).

Нам необходимо предотвратить выбор в качестве элементов независимого множест­ва таких узлов, которые представляют литералы, дополняющие друг друга. Поэтому, если есть два узла [ii,ji] и [i2,jV], один из которых представляет переменную х, а второй — х , то соединяем их ребром. Таким образом, их нельзя одновременно вы­брать в качестве элементов независимого множества.

Граница к для графа G, построенного по этим двум правилам, равняется т.

Легче ли проблемы, требующие ответа «да» или «нет»?

Может показаться, что «да/нет»-версия проблемы легче, чем исходная проблема оп­тимизации. Например, найти наибольшее независимое множество сложно, в то время как для данного небольшого значения границы к легко проверить, что существует не­зависимое множество размера к. Однако, возможно, нам дана константа к, представ­ляющая собой максимальный размер, для которого существует независимое множе­ство. Тогда для решения «да/нет»-версии проблемы необходимо найти максимальное независимое множество.

В действительности, все обычные NP-полные проблемы оптимизации и их «да/нет»- версии имеют эквивалентную сложность, по крайней мере, в пределах полиномиаль­ной зависимости. Например, если бы у нас был полиномиальный алгоритм, позво­ляющий найти максимальное независимое множество, то можно было бы решить «да/нет»-проблему, найдя максимальное независимое множество и проверив, что его размер не меньше предельного значения к. Поскольку, как мы покажем, «да/нет»- версия NP-полна, то и версия оптимизации должна быть трудно разрешимой. Сравнение можно провести и по-другому. Предположим, что у нас есть полиноми­альный алгоритм решения «да/нет»-проблемы НМ. Если граф имеет п узлов, то раз­мер максимального независимого множества заключен между 1 и п. Прогоняя алго­ритм решения НМ для всех возможных значений границы от 1 до п, мы, безусловно, найдем размер максимального независимого множества (но не обязательно само это множество) за время, необходимое для однократного решения НМ и умноженное на п. В действительности, с использованием бинарного поиска нам будет достаточно времени однократного решения, умноженного всего лишь на log₂п.

Граф G и границу к можно построить по формуле Е за время, пропорциональное квадрату длины Е, поэтому преобразование Е в G представляет собой полиномиальное сведение. Мы должны показать, что оно корректно сводит ЗВЫП к проблеме НМ, т.е.

• Е выполнима тогда и только тогда, когда G имеет независимое множество размера т.

(Достаточность) Во-первых, заметим, что независимое множество не может содер­жать два узла из одного и того же дизъюнкта, [г, //] и [г, j₂], где // + j₂, поскольку все та­кие узлы попарно соединены ребрами, как в столбцах на рис. 10.8. Поэтому, если суще­ствует независимое множество размера т, то оно содержит только по одному узлу из ка­ждого дизъюнкта.

Более того, независимое множество не может одновременно содержать узлы, которые соответствуют некоторой переменной х и ее отрицанию х , поскольку такие узлы попар­но соединены ребрами. Таким образом, независимое множество I размера т приводит к следующей подстановке Т, удовлетворяющей формуле Е. Если множеству I принадлежит узел, соответствующий переменной х, то Т(х) = I, а если узел, соответствующий отрица­нию х , то Г(х) = 0. Если / не содержит узла, который соответствовал бы х или х , то зна­чение Г(х) выбирается произвольно. Отметим, что пункт 2 приведенных выше правил объясняет, почему невозможно противоречие, когда узлы, соответствующие х и х, од­новременно принадлежат /.

Утверждаем, что Е истинна при Т. Для каждого дизъюнкта формулы Е существует узел в /, соответствующий одному из ее литералов, и подстановка Т выбрана так, что для нее этот литерал имеет значение «истина». Поэтому, если независимое множество разме­ра m существует, то Е выполнима.

(Необходимость) Допустим теперь, что Е истинна при некоторой подстановке Т. По­скольку при Т каждый дизъюнкт Е имеет значение «истина», можно выбрать из каждого дизъюнкта по одному литералу, истинному при подстановке Т. В некоторых дизъюнктах таких литералов может быть два или три, и тогда один из них выбирается произвольно. Строим множество /, состоящее из m узлов, соответствующих литералам, которые были выбраны из каждого дизъюнкта.

Утверждаем, что / является независимым множеством. Ребра между узлами из одного и того же дизъюнкта (столбцы на рис. 10.8) не могут иметь оба конца в /, так как из каж­дого дизъюнкта выбирается только по одному узлу. Оба конца ребра, соединяющего пе­ременную и ее отрицание, также не могут одновременно находиться в /, так как в I вы­браны только узлы, которые соответствуют литералам, истинным при подстановке Т. Безусловно, для Т либо х, либо х будет истинным, но не одновременно. Отсюда следует, что если Е выполнима, то G имеет независимое множество размера т.

Таким образом, существует полиномиальное сведение проблемы ЗВЫП к проблеме НМ. Поскольку известно, что проблема ЗВЫП NP-полна, то согласно теореме 10.5 про­блема НМ также NP-полна. □

Пример 10.19. Посмотрим, как конструкция теоремы 10.18 применяется к формуле

Е = (xi+ х₂ + x₃)(x_t + х₂ +х₄)( х₂ + xj + jc₅)( 5с₃ + х₄ + Зс₅).

Мы уже видели граф, полученный по данной формуле (см. рис. 10.8). Узлы расположены в четырех столбцах, соответствующих четырем дизъюнктам. Кроме обозначений узлов (пары целых чисел), указаны также соответствующие им литералы. Отметим, что все уз­лы одного столбца, соответствующие литералам из одного дизъюнкта, попарно соедине­ны ребрами. Кроме того, ребрами соединены узлы, соответствующие переменной и ее отрицанию. Так, узел [3, 1], соответствующий х₂, соединен с узлами [1,2] и [2, 2], соот­ветствующими вхождениям переменной х₂—

Жирными кружками выделено множество I из четырех узлов, по одному из каждого столбца. Они формируют независимое множество. Поскольку им соответствуют четыре литерала x_h х₂, х₃ и х₄, то по ним можно построить подстановку Т, в которой Т(х_;) = I, Т(х₂) = 1, Т(х₃) = 1 и Т(х₄) = 0. Нужно также приписать значение переменной х₅, но его можно выбрать произвольным образом, скажем, Г^-) = 0. Итак, формула Е истинна при Т, и множество узлов / указывает по одному литералу, истинному при Т, в каждом дизъюнкте. □

Для чего используются независимые множества

В цели данной книги не входит описание приложений тех проблем, NP-полнота кото­рых доказывается. Однако проблемы, рассмотренные в разделе 10.4, взяты из фунда­ментальной статьи Р. Карпа об NP-полноте, в которой он описал наиболее важные проблемы в области исследования операций и показал, что многие из них являются NP-полными. Таким образом, существует великое множество «реальных» проблем, решаемых с помощью абстрактных.

В качестве примера рассмотрим, как с помощью алгоритма поиска максимального независимого множества можно составить расписания экзаменов. Пусть узлы графа соответствуют различным предметам, и два узла соединяются ребром, если один или несколько студентов изучают оба эти предмета, и экзамены по этим предметам не мо­гут быть назначены на одно и то же время. Если мы найдем максимальное независи­мое множество, то сможем составить расписание так, чтобы экзамены по всем пред­метам из этого множества проходили одновременно, и ни у одного студента не было накладок.

10.4.3. Проблема узельного покрытия

Еще один важный класс проблем комбинаторной оптимизации касается «покрытия» графа. К примеру, реберное покрытие есть множество ребер, для которого каждый узел графа является концом хотя бы одного ребра из этого множества. Реберное покрытие яв­ляется минимальным, если оно содержит не больше ребер, чем любое реберное покрытие этого графа. Проблема, состоящая в выяснении того, имеет ли граф реберное покрытие из к ребер, здесь не рассматривается.

Докажем NP-полноту проблемы узельного покрытия. Узельное покрытие графа — это множество узлов, для которого хотя бы один конец любого ребра является узлом из этого множества. Узельное покрытие является минимальным, если оно содержит не больше узлов, чем любое узельное покрытие данного графа.

Узельные покрытия и независимые множества тесно связаны, поскольку дополнение независимого множества является узельным покрытием, и наоборот. Поэтому проблему НМ легко свести к проблеме узельного покрытия (УП), сформулировав последнюю должным образом в виде «да/нет»-проблемы.

Проблема. Проблема узельного покрытия (УП).

Вход. Граф G и верхняя граница к, значение которой заключено между 0 и числом, которое на 1 меньше числа узлов G.

Выход. Ответ «да» тогда и только тогда, когда G имеет узельное покрытие из к или меньшего числа узлов.

Проблема, сводящаяся к данной. Проблема независимого множества.

Теорема 10.20. Проблема узельного покрытия NP-полна.

Доказательство. Проблема УП, очевидно, принадлежит MV- Нужно угадать множе­ство из к узлов, и проверить для каждого ребра G, принадлежит ли хотя бы один его ко­нец этому множеству.

Для завершения доказательства сведем проблему НМ к проблеме УП. Идея, которую подсказывает рис. 10.8, состоит в том, что дополнение независимого множества есть узельное покрытие. К примеру, узлы на рис. 10.8, которые не выделены жирным, обра­зуют узельное покрытие. Поскольку выделенные узлы образуют максимальное незави­симое множество, то минимальное узельное покрытие образовано остальными узлами.

Сведение заключается в следующем. Пусть граф G с нижней границей к — экземпляр проблемы независимого множества. Если G имеет п узлов, то пусть G с верхней грани­цей п- к— тот экземпляр проблемы узельного покрытия, который мы строим. Это пре­образование, очевидно, может быть произведено за линейное время. Утверждаем, что

• G имеет независимое множество размера к тогда и только тогда, когда в G есть узельное покрытие из п- к узлов.

(Достаточность) Пусть N— множество узлов графа G, и пусть С— его узельное покрытие размера п — к. Утверждаем, что N-C есть независимое множество. Предполо­жим противное, т.е. что в N -С существует пара узлов v и w, соединенная ребром в G. Тогда, поскольку ни v, ни w не принадлежат С, ребро (v, w), принадлежащее G, не по­крывается предполагаемым узельным покрытием С. Таким образом, от противного дока­зано, что N — С является независимым множеством. Очевидно, это множество содержит к узлов, и в эту сторону утверждение доказано.

(Необходимость) Предположим, I— независимое множество, состоящее из к узлов. Утверждаем, что N — / — узельное покрытие графа G, состоящее из п — к узлов. Снова используем доказательство от противного. Если существует некоторое ребро (v, vv), не покрываемое множеством N -1, то и v, и w принадлежат I, но соединены ребром, а это противоречит определению независимого множества. □

10.4.4. Проблема ориентированного гамильтонова цикла

Мы хотим показать NP-полноту проблемы коммивояжера (ПКОМ), так как она пред­ставляет большой интерес с точки зрения комбинаторики. Наиболее известное доказа­тельство ее NP-полноты в действительности является доказательством NP-полноты бо­лее простой проблемы, называемой «проблемой гамильтонова цикла» (ГЦ). Проблема гамильтонова цикла описывается следующим образом.

Проблема. Проблема гамильтонова цикла.

Вход. Неориентированный граф G.

Выход. Ответ «да» тогда и только тогда, когда G имеет гамильтонов цикл, т.е. цикл, проходящий через каждый узел G только один раз.

Отметим, что проблема ГЦ — это частный случай проблемы ПКОМ, при котором вес каждого ребра имеет значение 1. Поэтому полиномиальное сведение ГЦ к ПКОМ уст­роено очень просто: нужно всего лишь уточнить, что каждое ребро графа имеет единич­ный вес.

Доказать NP-полноту проблемы ГЦ достаточно трудно. Вначале рассмотрим ограни­ченную версию проблемы ГЦ, в которой ребра имеют направления (т.е. являются на­правленными ребрами, или дугами), а гамильтонов цикл обходит граф в направлении, указываемом дугами. Сведем проблему ЗВЫП к этой ограниченной версии проблемы ГЦ, а затем сведем последнюю к обычной «неориентированной» версии ГЦ.

Проблема. Проблема ориентированного гамильтонова цикла (ОГЦ).

Вход. Ориентированный граф G.

Выход. Ответ «да» тогда и только тогда, когда в G есть ориентированный цикл, про­ходящий через каждый узел ровно один раз.

Проблема, сводящаяся к данной. Проблема ЗВЫП.

Теорема 10.21. Проблема ориентированного гамильтонова цикла NP-полна.

Доказательство. Доказать, что ОГЦ принадлежит классу MV, легко — нужно уга­дать цикл и проверить наличие его дуг в данном графе. Сведем проблему ЗВЫП к ОГЦ. Для этого потребуется построить довольно сложный граф, в котором подграфы специального вида представляют переменные и дизъюнкты данного экземпляра про­блемы ЗВЫП.

Начнем построение экземпляра ОГЦ по булевой формуле в ЗКНФ. Пусть формула имеет вид Е = ei а е₂ а ■•■ л е_к, где каждое е, — дизъюнкт, представляющий собой сумму

Рис. 10.9. Построение, используемое в доказательстве NP-полноты проблемы гамильтонова цикла

трех литералов, скажем, е, = {а_и + a_l2 + a_i3). Пусть x_h х₂, …, х„ — переменные в формуле Е. Для всех дизъюнктов и переменных строятся подграфы, как показано на рис. 10.9.

Для каждой переменной х, строится подграф Н„ структура которого показана на рис. 10.9, а. Здесь m_t— большее из чисел вхождений х, и Зс, в Е. Узлы с,у и b_tJ, располо­женные в двух столбцах, соединены между собой дугами в обоих направлениях. Кроме того, каждое Ь имеет дугу, ведущую в с, расположенное на ступеньку ниже, т.е., если j < m,, то b,j имеет дугу, ведущую в c_v/. Аналогично, если j < /и„ то с,у имеет дугу, веду­щую в bjj^. Наконец, есть верхний узел а,, из которого дуги ведут в Ь_ю и с_ю, и нижний узел d_h в который ведут дуги из Ь,_т, и c_imr

На рис. 10.9, б показана структура графа в целом. Каждый шестиугольник представ­ляет один подграф, построенный для переменной (его структура показана на рис. 10.9, а). Шестиугольники расположены циклически, и из нижнего узла каждого под­графа дуга ведет в верхний узел следующего.

Допустим, граф на рис. 10.9, б имеет ориентированный гамильтонов цикл. Не огра­ничивая общности, можно считать, что этот цикл начинается в а/. Если затем он перехо­дит в Ью, то на следующем шаге он обязательно перейдет в с/о (иначе сю не появится в цикле). В самом деле, если цикл переходит из a_t в Ью, а затем — в сц, то Сю никогда не появится в цикле, поскольку оба его предшественника (а₀ и Ью) уже содержатся в нем.

Таким образом, если начало цикла имеет вид 0[, Ью, то далее он должен спускаться «лесенкой», переходя из стороны в сторону:

<3/, Ь₁₀, Сю, Ьц, сц, …, bi_ml, c_lmi, dj. Если начало цикла имеет вид а,, сю, то в лесенке меняется порядок предшествования с и Ь:

^аи ^сю, Ью, Сц, Ьц,…, ci_ml, bi_m„ d_t. Решающим пунктом в доказательстве является то, что порядок, при котором спуск со­вершается от с к Ь, можно трактовать как приписывание переменной, соответствующей данному подграфу, значения «истина», а порядок, при котором спуск совершается от Ь к с, соответствует приписыванию этой переменной значения «ложь».

Закончив обход подграфа Hi, цикл должен перейти в а₂, где снова возникает выбор следующего перехода — в Ь₂о или в с₂₀. Однако в силу тех же аргументов, которые при­ведены для Hi, после того, как сделан выбор направления вправо или влево от а₂, путь обхода Н₂ уже зафиксирован. Вообще, при входе в каждый Я/ есть выбор перехода влево или вправо, но никакого другого. Иначе некоторый узел обречен быть недоступным, т.е. он не сможет появиться в ориентированном гамильтоновом цикле, поскольку все его предшественники появились в нем ранее.

В дальнейшем это позволит нам считать, что выбор перехода из а, в Ь_ю означает при­писывание переменной х, значения «истина», а перехода из а, в с,₀ — значения «ложь». Поэтому граф на рис. 10.9, б имеет 2″ ориентированных гамильтоновых циклов, соответ­ствующих 2″ возможным подстановкам для п переменных.

Однако на рис. 10.9, б изображен лишь скелет графа, порождаемого по формуле Е, находящейся в 3-КНФ. Каждому дизъюнкту е, ставится в соответствие подграф /, (рис. 10.9, в). Он обладает тем свойством, что если цикл входит в rj, то должен выходить из iij, а если входит в s_p то выходит из v,, и если входит в t_p то выходит из Wj. Действи­тельно, если, достигнув Ij, цикл выходит из узла, расположенного не под входным узлом, то один или несколько узлов оказываются недоступными — они никак не могут появить­ся в цикле. В силу симметрии достаточно рассмотреть ситуацию, когда rj — первый узел из Ij в цикле. Возможны три варианта.

• Следующие два узла в цикле — Sj и t_r Если затем цикл переходит в w_; и выходит, то узел Vj оказывается недоступным. Если цикл переходит в w_t и vj, а затем выходит, то uj оказывается недоступным. Таким образом, цикл должен выходить из и_р обойдя предварительно все шесть узлов данного подграфа.
• Следующие после г, узлы — Sj и v_;. Если затем цикл переходит в и_р то узел w, оказы­вается недоступным. Если после и, цикл переходит в w_p то tj никогда не попадет в цикл по причине, «обратной» причине недоступности. В этой ситуации в tj можно попасть извне, но если tj войдет в цикл позже, то цикл нельзя будет продолжить, так как оба потомка tj уже появлялись в цикле ранее. Таким образом, и в этом случае цикл выходит из Отметим, однако, что tj и wj непроходимы слева; они должны появиться в цикле позже, что возможно.
• Цикл переходит из г/ прямо в и_р Если цикл переходит затем в Wj, то tj не сможет поя­виться в цикле, поскольку оба его потомка уже там есть, о чем говорилось при вари­анте 2. Таким образом, цикл должен сразу выходить из и_Р Оставшиеся четыре узла должны войти в цикл позже.

В завершение построения графа G для формулы Е соединяем подграфы I и Н сле­дующим образом. Допустим, у дизъюнкта е, первым литералом является х„ переменная без отрицания. Выберем некоторый узел с,_р, где р от 0 до от, — 1, ранее не использован­ный для соединения с подграфами I. Введем дуги, ведущие из с,_р в и из u_t в Ь,_р ,. Если же первым литералом дизъюнкта е, является отрицание 5с,, то нужно отыскать неисполь­зованный узел b_ip, а затем соединить Ь,_р с rj и и, с с,,_р+/.

Для второго и третьего литералов е, граф дополняется точно так же, за одним ис­ключением. Для второго литерала используются узлы Sj и v_p а для третьего — tj и Wj. Таким образом, каждый Ij имеет три соединения с подграфами типа Я, которые пред­ставляют переменные, присутствующие в дизъюнкте ej. Если литерал не содержит от­рицания, то соединение выходит из с-узла и входит в А-узел, расположенный ниже, а если содержит — соединение выходит из Ь-узла, возвращаясь в расположенный ниже с-узел. Мы утверждаем, что

• построенный таким образом граф G имеет ориентированный гамильтонов цикл тогда и только тогда, когда формула £ выполнима.

(Достаточность) Предположим, существует подстановка Т, удовлетворяющая фор­муле Е. Построим ориентированный гамильтонов цикл следующим образом.

• Вначале выберем путь, обходящий только подграфы Я (т.е. граф, изображенный на рис. 10.9, б) в соответствии с подстановкой Т. Таким образом, если Т(х,) = 1, то цикл переходит из я, в b_i0, а если Т(х) = 0, то он переходит из а, в с,₀—
• Однако цикл, построенный к данному моменту, может содержать дугу из b_ip в с,_р. _h причем у b_ip есть еще одна дуга в один из подграфов 1_р который пока не включен в цикл. Тогда к циклу добавляется «крюк», который начинается в b_ip, обходит все шесть узлов подграфа и возвращается в с,_р.,. Дуга b_ip —> с,_р , исключается из цик­ла, но узлы на ее концах остаются в нем.
• Аналогично, если в цикле есть дуга из c_ip в Ь,_{р h} и у с,_р есть еще одна дуга в один из 1р пока не включенных в цикл, то к циклу добавляется «крюк», проходящий через все шесть узлов 7,.

Тот факт, что Т удовлетворяет формуле Е, гарантирует, что исходный путь, построенный на шаге 1, будет содержать, по крайней мере, одну дугу, которая на шаге 2 или 3 позво­лит включить в цикл подграф 1_} для каждого дизъюнкта е,. Таким образом, цикл включа­ет в себя все подграфы Ij и является ориентированным гамильтоновым.

(Необходимость) Предположим, что граф G имеет ориентированный гамильтонов цикл, и покажем, что формула Е выполнима. Напомним два важных пункта из предыдущего анализа.

• Если гамильтонов цикл входит в некоторый /, в узле r_p s, или t_p то он должен выхо­дить из него в узле и_р v, или w_p соответственно.
• Таким образом, рассматривая данный гамильтонов цикл как обход подграфов типа Я, (см. рис. 10.9, б), можно характеризовать «экскурсию», совершаемую в некоторое 1_Р как переход цикла по дуге, «параллельной» одной из дуг Ь,_р —> с,_р., или с,_р —> b,_p. _h

Если игнорировать экскурсии в подграфы J_p то гамильтонов цикл должен быть одним из 2″ циклов, которые возможны с использованием только подграфов Н, и соответствуют выбо­рам переходов из а, либо в Ь,₀, либо в с_ш. Каждый из этих выборов соответствует приписыва­нию значений переменным из Е. Если один из них дает гамильтонов цикл, включающий под­графы 1_р то подстановка, соответствующая этому выбору, должна удовлетворять формуле Е.

Причина в том, что если цикл переходит из а, в Ь,₀, то экскурсия в Ij может быть со­вершена только тогда, когда j-й дизъюнкт содержит д:, в качестве одного из литералов. Если цикл переходит из а, в с,₀, то экскурсия в /₇ может быть совершена только тогда, ко­гда I, является литералом в j-м дизъюнкте. Таким образом, из того, что все подграфы Ij могут быть включены в граф, следует, что при данной подстановке хотя бы один из ли­тералов в каждом дизъюнкте истинен, т.е. формула Е выполнима. □

Пример 10.22. Приведем очень простой пример конструкции из теоремы 10.21, осно­ванный на формуле в 3-КНФ Е = (х,+ х₂+ х₃)(х^ + х₂ + хД Граф, который при этом строится, изображен на рис. 10.10. Дуги, соединяющие подграфы Я-типа с подграфами I- типа, показаны пунктиром исключительно для удобочитаемости, в остальном они ничем не отличаются от сплошных дуг.

Рис. 10.10. Пример построения гамильтонова цикла 10.4. КТТТЕ НЕСКОЛЬКО NP-ПОЛНЫХ ПРОБЛЕМ

Слева вверху виден подграф, соответствующий х/. Поскольку х/ встречается по одно­му разу в чистом виде и с отрицанием, достаточно одной ступеньки «лесенки». Поэтому здесь присутствуют две строки из узлов Ъ и с. Слева внизу виден подграф, соответст­вующий х₃, которая дважды встречается в чистом виде и ни разу с отрицанием. Поэтому необходимы две различные дуги с_3р —> b_3p._h с помощью которых можно присоединить подграфы // и 1₂ для дизъюнктов е/ и е₂, чтобы представить присутствие х₃ в этих дизъ­юнктах. Поэтому в подграфе для х₃ нужны три строки из узлов b и с.

Рассмотрим подграф 1₂, соответствующий дизъюнкту (5с, + х₂ + х₃). Для первого ли­терала Зс, к Ь/о присоединяется г₂, а к и₂ — сц. Для второго литерала то же самое проис­ходит с b₂₀, s₂, v₂ и с₂₁. Поскольку третий литерал не содержит отрицания, то он прикреп­ляется к узлам с и Ь, находящимся ниже, т.е. к с₃₁ присоединяется t₂, и к w₂ — b₃₂.

Одна из нескольких удовлетворяющих подстановок имеет вид х/ = 1, х₂ = 0 и jcj = 0. При данной подстановке первый дизъюнкт истинен благодаря первому литералу x_t, а второй — благодаря второму литералу х₂. Для этой подстановки можно построить га­мильтонов цикл, в котором присутствуют дуги Я/ —> Ь/о, а₂ —> с₂о и а₃ —> с₃о■ Цикл покры­вает первый дизъюнкт, совершая «крюк» из Hi в //, т.е. использует дугу с/о —» п, обходит все узлы в/, и возвращается в b,_h Второй дизъюнкт покрывается «крюком» из Н₂ в 1₂, который начинается переходом по дуге b₂₀ s₂, затем обходит все узлы 1₂ и возвращает­ся в c₂i. Весь гамильтонов цикл выделен более жирными линиями (сплошными или пунктирными) и крупными стрелками (см. рис. 10.10). □

10.4.5. Неориентированные гамидьтоновы циклы и ПКОМ

Доказательства NP-полноты проблем неориентированного гамильтонова цикла и коммивояжера относительно просты. В разделе 10.1.4 мы уже убедились, что ПКОМ принадлежит классу NP. Проблема ГЦ представляет собой частный случай ПКОМ, так что она тоже принадлежит NV. Сведем ОГЦ к ГЦ и ГЦ к ПКОМ.

Проблема. Проблема неориентированного гамильтонова цикла.

Вход. Неориентированный граф G.

Выход. Ответ «да» тогда и только тогда, когда G имеет гамильтонов цикл.

Проблема, сводящаяся к данной. ОГЦ.

Теорема 10.23. Проблема ГЦ NP-полна.

Доказательство. ОГЦ сводится к ГЦ следующим образом. Пусть дан ориентирован­ный граф Gj. По нему строится неориентированный граф, который обозначается G_u. Ка­ждому узлу v графа Gj соответствуют три узла графа G_u — v₀, V/ и v₂. Граф G_u содержит следующие ребра.

• Каждому узлу v графа G_d в графе G_u соответствуют ребра (v⁽⁰⁾, v⁽¹⁾) и (v⁽¹⁾, v^t2>).
• Если Gj содержит дугу х —> w, то G_u содержит ребро (\Р\ w⁽⁰⁾).

На рис. 10.11 представлен набор ребер, включая ребро, соответствующее дуге v —» w.

Рис. 10.11. Дуги G_d заменяются в G_u ребрами, которые ведут от узлов с индексом 2 к узлам с индексом О

Построение G_u по G_d, очевидно, выполнимо за полиномиальное время. Нужно показать, что

• G_u имеет гамильтонов цикл тогда и только тогда, когда Gj имеет ориентирован­ный гамильтонов цикл.

(Достаточность) Пусть v_;, v₂, …, v,„ v_t— ориентированный гамильтонов цикл. То­гда, безусловно,

v/⁰⁾, v/», v/²>, v/>, v/²>, v/⁰⁾,..„ v„⁽¹>, V®, v/°> есть неориентированный гамильтонов цикл в G„. Таким образом, происходит спуск по каж­дому столбцу, а затем скачок на вершину следующего столбца, соответствующий дуге в Gj.

(Необходимость) Отметим, что каждый узел v⁽¹⁾ в G_u имеет два ребра, и поэтому он должен присутствовать в гамильтоновом цикле вместе с узлами v^<0) и v⁽²⁾ — непосредст­венными предшественником и потомком. Таким образом, гамильтонов цикл в G_u должен содержать узлы, индексы которых образуют последовательность 0, 1, 2, 0, 1, 2, … или наоборот— 2, 1, 0, 2, 1, 0, …. Поскольку эти последовательности соответствуют обхо­дам цикла в противоположных направлениях, то для определенности можно предпола­гать, что эта последовательность имеет вид 0, 1, 2, 0, 1, 2, …. Из построения G„ следует, что ребра этого цикла, которые выходят из узлов с индексом 2 и входят в узлы с индек­сом 0, являются дугами в G_A и направление обхода таких ребер совпадает с направлени­ем соответствующих дуг. Таким образом, существование неориентированного гамильто- нова цикла в G„ влечет существование ориентированного гамильтонова цикла в G_rf. □

Проблема. Проблема коммивояжера.

Вход. Неориентированный граф G, ребра которого имеют целочисленный вес, и пре­дельное значение к.

Выход. Ответ «да» тогда и только тогда, когда G имеет гамильтонов цикл, общий вес ребер которого не превышает к.

Проблема, сводящаяся к данной. ГЦ.

Теорема 10.24. Проблема коммивояжера NP-полна.

Доказательство. Проблема ГЦ сводится к ПКОМ следующим образом. По данному графу G строится взвешенный граф G’, который имеет те же узлы и ребра, что и G, и ка­ждое ребро имеет вес 1. Предельное значение к берется равным п — числу узлов G. Та­ким образом, в G’ существует гамильтонов цикл с весом п тогда и только тогда, когда существует гамильтонов цикл в G. □

10.4.6. Вывод относительно NP-полных проблем

Все сведения, построенные в данной главе, показаны на рис. 10.12. Заметим, что для всех специфических проблем (например ПКОМ) было представлено их сведение к ВЫП. Язык любой недетерминированной машины Тьюринга с полиномиальным временем в теореме 10.9 был сведен к проблеме ВЫП. Среди этих МТ была хотя бы одна, решающая ПКОМ, хотя бы одна, решающая НМ, и так далее, но они не указывались явно. Таким образом, все NP-полные проблемы полиномиально сводимы друг к другу, и, следова­тельно, представляют собой разные формы одной и той же проблемы.

Все из NP Рис. 10.12. Схема сведений NP-полных проблем

Т0.4.7. Упражнения к разделу Т0.4

(*) к-кликой в графе G называется множество из к узлов графа G, каждые два узла которого соединены ребром. Таким образом, 2-клика— это просто пара узлов, связанных ребром, а 3-клика — треугольник. Проблема клики (КЛИКА) состоит в том, чтобы: по данному графу G и константе к выяснить, содержит ли он к-клику. Выполните следующее:

а)   найдите наибольшее значение к, при котором граф на рис. 10.1 принадлежит проблеме клики;

б)  укажите зависимость количества ребер к-клики от к;

в)   докажите NP-полноту проблемы клики, сведя к ней проблему узельного покрытия.

(*!) Проблема раскраски состоит в том, чтобы для данного графа G и целого числа к выяснить, является ли G «^-раскрашиваемым», т.е. каждому узлу G мож­но приписать один из к цветов так, что никакие два узла, связанные ребром, не будут окрашены в один цвет. Например, граф на рис. 10.1 является 3-раскра- шиваемым, поскольку узлам 1 и 4 можно приписать красный цвет, узлу 2 — зе­леный, а 3 — синий. Вообще, если граф имеет к-клику, то он не может быть ме­нее, чем /^-раскрашиваемым, хотя, возможно, для его раскраски нужно намного больше, чем к цветов.

В этом упражнении приводится часть конструкции, доказывающей NP-полноту проблемы раскраски. Оставшуюся часть восстановите самостоятельно. К данной проблеме сводится проблема ЗВЫП. Предположим, у нас есть формула в 3-КНФ с п переменными. Сведение переводит эту формулу в граф, часть которого изо­бражена на рис. 10.13. Как видим, слева находятся n + 1 узлов с₀, c_h …, с„, обра­зующих (и + 1)-клику. Поэтому все эти узлы должны быть раскрашены в разные цвета. Цвет, приписанный узлу с_р мы будем называть «цветом с».

Каждой переменной х, соответствуют два узла, которые можно обозначить как x_t и х,. Они соединены ребром, и поэтому не могут быть окрашены в один и тот же цвет. Кроме того, каждый узел х, соединен с c_t для всех j, не равных 0 и /. Следовательно, один из узлов х, и х, должен иметь цвет с₀, а другой — цвет с,. Будем считать, что литерал в узле цвета с₀ истинен, а во втором узле — ложен. Таким образом, выбранная раскраска отвечает некоторой подстановке. Для завершения доказательства нужно построить для каждого дизъюнкта фор­мулы соответствующий фрагмент графа. Завершить раскраску, используя только цвета от с₀ до с„, должно быть возможно тогда и только тогда, когда каждый дизъюнкт формулы имеет значение «истина» при подстановке, соответствующей этому выбору цветов. Таким образом, построенный граф является (n + 1 )- раскрашиваемым тогда и только тогда, когда данная формула выполнима.

Рис. 10.13. Часть построения, показывающего NP-полноту проблемы раскраски 10.4.3. (!) Даже для относительно небольших графов NP-полные проблемы бывает очень трудно решить вручную. Рассмотрим граф на рис. 10.14: а)                   (*) имеет ли этот граф гамильтонов цикл? б)                   каково максимальное независимое множество в этом графе?

в)   что представляет собой наименьшее узельное покрытие этого графа?

г)    каково наименьшее реберное покрытие этого графа (см. упражнение 10.4.4, в)?

д)   является ли этот граф 2-раскрашиваемым?

10.4.4. Докажите NP-полноту следующих проблем.

а)   Проблема изоморфизма подграфа. Даны графы G_t и G₂. Содержит ли G_t копию G₂ в качестве подграфа, т.е. можно ли найти в G/ подмножество уз­лов, которые вместе с ребрами, инцидентными им в G/, при правильном выборе соответствия между ними и узлами G₂ образуют точную копию графа Gfl Указание. Рассмотрите сведение проблемы клики из упражне­ния 10.4.1 к данной.

б)   (!) Проблема реберного покрытия обратных связей. Даны граф G и целое число к. Имеет ли G подмножество из к ребер, для которого каждый цикл в G содержит хотя бы одно его ребро?^[6]

в)   (!) Задача линейного целочисленного программирования. Задано множество линейных ограничений-неравенств                                                                                     < с или                   > с, где а, и с —

целочисленные константы, а х/, х₂, …, х„— переменные. Существует ли на­бор целых значений этих переменных, при котором верны все ограничения- неравенства?

г)   (!) Проблема доминирующего множества. Даны граф G и целое число к. Существует ли в G подмножество S, состоящее из к узлов, каждый узел кото­рого либо принадлежит S, либо имеет в S смежный узел?

д)   Проблема пожарных депо. Даны граф G, расстояние d и некоторое коли­чество /»пожарных депо». Можно ли в G выбрать/узлов так, чтобы рас­стояние (число ребер, которые нужно пройти, чтобы попасть из одного узла в другой) от любого узла до некоторого пожарного депо не превы­шало dl

е)   (*!) Проблема половинной клики. Дан граф G с четным числом узлов. Суще­ствует ли в G клика (см. упражнение 10.4.1), содержащая ровно половину уз­лов G? Указание. Сведите проблему клики к проблеме половинной клики. Вам нужно представить, каким образом следует добавлять узлы, чтобы наи­большая клика содержала нужное число узлов.

ж)  (V.) Проблема расписания с единичным временем выполнения. Даны к «заданий» 7>, Т₂, …, Т_ь число «процессоров» р, предел времени t и

«ограничения предшествования» вида Г, < 7} между парами заданий^[7]. Суще­ствует ли расписание выполнения заданий со следующими свойствами?

Каждое задание назначено на одну единицу времени между 1 и t.

На каждую единицу времени назначено не более р заданий.

Учтены ограничения предшествования: если существует ограничение Т, < Tj, то задание Т, назначено на более раннюю единицу времени, чем 7}.

з)    (!!) Проблема точного покрытия. Дано множество S и набор его подмно­жеств Sj, S₂, …, S„. Можно ли указать набор множеств Тс {Sj, S₂, …, 5,,} так, чтобы каждый элемент х множества S принадлежал ровно одному из элемен­тов набора 77

и)   (!!) Проблема разбиения. Можно ли разбить данный список из к целых чисел ij, i₂, …, i_k на две части с одинаковыми суммами элементов? Указание. На первый взгляд, эта проблема принадлежит классу V, поскольку можно пред­положить, что сами целые числа невелики. Действительно, если эти целые числа ограничены полиномом относительно количества чисел к, то сущест­вует полиномиальный алгоритм решения. Однако в списке из к целых чисел в двоичной системе, имеющем общую длину п, могут быть элементы, значе­ния которых почти экспоненциальны относительно п.^[8]

10.4.5. Гамильтонов путь в графе G есть упорядочение всех узлов п_:, п₂, …, п_к, при ко­тором для каждого /=1,2, …, к — 1 существует ребро из п, в «,. /• Ориентиро­ванный гамильтонов путь — это то же самое для ориентированного графа (должна существовать дуга из п, в п, .,). Отметим, что условия гамильтонова пу­ти лишь немного слабее условий, налагаемых на гамильтонов цикл. Проблема (ориентированного) гамильтонова пути состоит в следующем: имеет ли данный (ориентированный) граф хотя бы один (ориентированный) гамильтонов путь?

а) (*) Докажите, что проблема ориентированного гамильтонова пути NP-полна. Указание. Сведите проблему ОГЦ к данной. Выберите произвольный узел и разбейте его на два узла так, чтобы они были конечными точками ориенти­рованного гамильтонова пути, и чтобы этот путь существовал тогда и только тогда, когда исходный граф имеет ориентированный гамильтонов цикл.

б)   Покажите, что проблема неориентированного гамильтонова пути NP-полна. Указание. Используйте конструкцию из теоремы 10.23.

в)   (*!) Покажите NP-полноту следующей проблемы: по данным графу G и це­лому числу к выяснить, имеет ли G остовное дерево, число листьев которого не более к. Указание. Сведите проблему гамильтонова пути к данной.

г)   (!) Покажите NP-полноту следующей проблемы: по данным графу G и цело­му числу d выяснить, имеет ли G остовное дерево, в котором степень любого узла не превышает d? (Степенью узла я в остовном дереве называется число ребер этого дерева, инцидентных п.)

10.5. Резюме

Классы V и MP. Класс V состоит из всех языков или проблем, допускаемых ма­шинами Тьюринга, время работы которых полиномиально зависит от длины вхо­да. MP— это класс языков или проблем, допускаемых недетерминированными МТ, у которых время работы при любой последовательности недетерминирован­ных выборов полиномиально ограничено.

Вопрос о V = MP. Точно не известно, различны ли классы языков V и MP. Но есть серьезные основания полагать, что в MP есть языки, не принадлежащие V.

Полиномиальные сведения. Если экземпляры одной проблемы преобразуемы за полиномиальное время в экземпляры другой, дающие тот же ответ («да» или «нет»), то говорят, что первая проблема полиномиально сводится ко второй.

MP-полные проблемы. Язык является NP-полным, если он принадлежит MP и вся­кий язык из MP можно полиномиально свести к нему. Мы верим в то, что ни одна из NP-полных проблем не принадлежит Р. Тот факт, что ни для одной из тысяч известных NP-полных проблем до сих пор не найден полиномиальный алгоритм разрешения, только укрепляет нашу уверенность.

NP-полная проблема выполнимости. В теореме Кука была показана NP-полнота про­блемы выполнимости булевой формулы (ВЫП). Доказательство проводилось путем сведения любой проблемы из MP к проблеме ВЫП. Кроме того, проблема выполни­мости остается NP-полной, даже если вид формулы ограничен произведением сомно­жителей, каждый из которых содержит лишь три литерала (проблема ЗВЫП).

Другие NP-полные проблемы. NP-полнота очень многих проблем доказывается пу­тем сведения к ним других проблем, о которых заранее известно, что они NP- полные. Здесь приведены сведения, доказывающие NP-полноту проблем незави­симого множества, узельного покрытия, ориентированного и неориентированного гамильтонова цикла, а также коммивояжера.

10.6. Литература

Понятие NP-полноты как свидетельство того, что проблему нельзя решить за поли­номиальное время, и доказательство NP-полноты ВЫП, ВКНФ и ЗВЫП впервые были приведены в работе С. Кука [3]. За ней последовала не менее важная статья Р. Карпа [6], в которой было показано, что NP-полнота — это не изолированный феномен; она при­суща многим трудным комбинаторным проблемам, изучавшимся долгие годы в исследо­вании операций и других дисциплинах. Из этой статьи взяты все проблемы, NP-полнота которых доказана в разделе 10.4 — независимое множество, узельное покрытие, гамиль­тонов цикл и коммивояжер. Кроме того, в ней можно найти решения некоторых про­блем, рассмотренных в упражнениях: реберное покрытие обратных связей, разбиение, раскраска и точное покрытие.

В книге Гэри и Джонсона [4] собрано воедино большое число фактов, касающихся NP-полноты различных проблем, а также приведены их частные случаи, разрешимые за полиномиальное время. В [5] содержатся статьи об аппроксимации решения NP-полной проблемы за полиномиальное время.

Необходимо упомянуть еще несколько работ, послуживших серьезным вкладом в теорию NP-полноты. Первые исследования классов языков, определяемых временем ра­боты машин Тьюринга, были предприняты Хартманисом и Стирнзом [8]. Кобхем [2] первым выделил класс V как понятие, в котором отражено коренное отличие от алгорит­мов, имеющих конкретное полиномиальное время работы, например 0(п²). Несколько позже (но независимо) идею NP-полноты исследовал Левин [7].

NP-полнота задачи линейного целочисленного программирования (упражнение 10.4.4, в) появилась в работе [1], а также в неопубликованных заметках Дж. Гатена (J. Gathen) и М. Зивекинга (М. Sieveking). NP-полнота проблемы расписания с единич­ным временем выполнения (упражнение 10.4.4, ж) доказана в [9].

304. Borosh and L. В. Treybig, «Bounds on positive integral solution of linear Diophantine equations», Proceedings of the AMS 55 (1976), pp. 299-304.
305. Cobham, «The intrinsic computational difficulty of functions», Proc. 1964 Congress for Logic, Mathematics, and the Philosophy of Science, North Holland, Amsterdam, pp. 24-30.
306. C. Cook, «The complexity of theorem-proving procedures», Third ACM Symposium on Theory of Computing (1971), ACM, New York, pp. 151-158. (Кук С. Сложность проце­дур вывода теорем. — Кибернетический сборник, новая серия, вып. 12. — М.: Мир, 1975, —С. 5-15.)

М. R. Garey and D. S. Johnson, Computers and Intractability: a Guide to the Theory of NP-Completeness, H. Freeman, New York, 1979. (ГэриМ., Джонсон Д. Вычислитель­ные машины и труднорешаемые задачи. — М.: Мир, 1982.)

1996. S. Hochbaum (ed.), Approximation Algorithms for NP-Hard Problems, PWS Publishing Co., 1996.
1997. M. Karp, «Reducibility among combinatorial problems», in Complexity of Computer Computations (R.E.Miller, ed.), Plenum Press, New York, (1972), pp. 85-104. (Карп P. M. Сводимость комбинаторных проблем. — Кибернетический сборник, но­вая серия, вып. 12. — М.: Мир, 1975. — С. 16-38.)

Л. А. Левин. Универсальные проблемы упорядочения // Проблемы передачи инфор­мации. — 1973. — Т. 9, № 3. — С. 265-266.

306. Hartmanis and R. Е. Stearns, «On the computational complexity of algorithms», Transactions oftheAMSUl (1965), pp. 285-306.
307. D. Ullman, «NP-complete scheduling problems», J. Computer and System Sciences 10:3 (1975), pp. 384-393.

^[1]Это утверждение не совсем верно. В действительности мы лишь предполагаем, что Pi не при­надлежит V, на том весьма веском основании, что Р/ является «NP-полной» (понятие «NP- полноты» обсуждается в разделе 10.1.6). Затем мы доказываем, что Р, также является «NP-полной» и, таким образом, не принадлежит V на том же основании, что и Р/.

^[2] С общим набором переменных. — Прим. перев.

^[3] В силу п. 2 не обязательно даже, чтобы S(x) = Т(х) при тех х, для которых Т(х) определено. — Прим. ред.

^[4] В данном конкретном случае, когда подформула у + z уже является дизъюнктом, можно не выполнять общее построение дизъюнкта для логического ИЛИ формул, а взять (у + z) в качест­ве произведения дизъюнктов, эквивалентного у + z. Однако здесь мы строго придерживаемся общих правил.

^[5] Для удобства, говоря о литералах, считаем их переменными без отрицания, например х. Но все наши построения остаются в силе и в том случае, когда некоторые или все литералы являются отрицаниями переменных, например х .

^[6] В этом месте оригинал книги содержал формулировку проблемы реберного покрытия, кото­рая в действительности полиномиальна. Исправление ошибки было выставлено авторами в Internet (см. предисловие). — Прим. ред.

^[7] Неявно предполагается, что ограничения предшествования являются отношением частичного порядка. — Прим. ред.

^[8] В оригинале данная проблема была названа «задачей о ранце » (knapsack problem), хотя послед­няя имеет такой вид: «Существует ли для данной последовательности целых чисел S = ij, i₂, …,i„ и целого числа к подпоследовательность в S, сумма членов которой равна к?». Очевидно, что про­блема разбиения является частным случаем задачи о ранце при =2к . — Прим. ред.