Труднорешаемые задачи

Как уже говорилось выше, общепринятой является точка зрения, согласно которой алгоритм считается эф­фективным, если он имеет полиномиальную сложность. Именно таковы все алгоритмы, рассмотренные в преды­дущих параграфах. Заметим, однако, что за пределами этих рассмотрений осталась большая часть важных за­дач. Это, в частности, задачи отыскания в графе наиболь­шего независимого множества, гамильтонова цикла, k-раскраски и ряд других. Все они характеризовались нами как очень трудные еще до того, как мы приступили к обсуждению алгоритмов. Дело в том, что, несмотря на усилия многих специалистов, для решения подобных задач до сих пор не найдено полиномиальных алгорит­мов. Более того, имеются веские доводы, позволяющие предположить, что таких алгоритмов не существует. Об­суждению этих доводов и посвящен данный параграф. Начнем с внесения изменений в вычислительную мо­дель. Будем считать, что каждая ячейка абстрактной вы­числительной машины может содержать только 0 или 1, и целые числа рассматриваются в двоичной системе счис­ления. В соответствии с этим всякое целое число а ≠ 0,1 займет ]log|α|[ ячеек машинной памяти (]х[— наименьшее целое, не меньшее чем х). Рациональное число, не являющееся целым, будем рассматривать в ви­де несократимой дроби и представлять в машине как упорядоченную пару целых чисел — числитель и знаме­натель этой дроби. Время выполнения каждой элемен­тарной операции примем равным сумме длин записей ее операндов в двоичной системе счисления.

Далее будем рассматривать каждую задачу в так на­зываемом распознавательном варианте, когда решение задачи заключается в получении ответа «да» или «нет». Всякий алгоритм решения такой задачи, будучи приме­ненным к соответствующему виду, работает какое-то время и затем, сообщив ответ «да» либо «нет», останав­ливается. Для некоторых задач их «естественные» поста­новки уже являются распознавательными. Таковы, на­пример, задачи распознавания изоморфизма, изоморфной вложимости, гамильтоновости, планарности, эйлеровости графов. Однако чаще (а на практике — как правило) ис­ходная постановка задачи является оптимизационной. В оптимизационной задаче требуется выбрать из множе­ства допустимых решений X такое решение х, вес (или стоимость) которого w{x) минимален. В рассмотренных нами оптимизационных задачах в качестве X фигуриро­вали множества остовов, путей с заданной начальной вершиной или паросочетаний данного графа. Каждой оп­тимизационной задаче сопоставим ее распознавательный вариант, который выглядит следующим образом. По за­данным множеству X, весовой функции w и числу k тре­буется определить, существует ли элемент х € Х такой, что w(x) ≤ k. Очевидно, что имея полиномиальный алго­ритм решения оптимизационной задачи, легко получить полиномиальный алгоритм решения соответствующей ей распознавательной задачи. Можно показать, что при до­вольно необременительных предположениях относительно функции w верно и обратное. Мы не будем на этом останавливаться, поскольку для дальнейшего нам доста­точно только знать, что оптимизационная задача «не проще» соответствующей распознавательной.

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

Теперь сделаем следующее важное наблюдение. Все задачи, с которыми мы сталкивались до сих пор, неза­висимо от того, установлена их принадлежность классу Р или нет, обладают одним общим свойством: если вход задачи таков, что имеет место ответ «да», то существует полиномиальный алгоритм, доказывающий этот факт. Поясним сказанное на примере. Пусть задача состоит в выяснении, является ли граф гамильтоновым, и пусть поступающий на вход граф G гамильтонов, т. е. в графе G имеется гамильтонов цикл С. Тогда доказательство гамильтоновости графа G заключалось бы в проверке включения C € G. Если, например, граф G задан матри­цей смежности, то эту проверку можно выполнить с по­мощью очевидного алгоритма, затратив О(п) операций. Подчеркнем, что речь идет лишь о существовании поли­номиального доказательства — чтобы иметь это доказа­тельство в своем распоряжении, надо знать цикл С. Положение иное, если граф G не является гамильтоно­вым. В этом случае нельзя утверждать даже, что полино­миальное доказательство этого факта существует. Можно, конечно, перебрать все (|G| — 1)! простых циклов длины |G| полного графа, проверяя каждый раз, содержится ли цикл в графе G. Однако подобное доказательство требует времени по крайней мере O((|G| — 1)!), и, следователь­но, не является полиномиальным.

Теперь мы хотим определить еще один класс распо­знавательных задач, включив в него все задачи, облада­ющие тем свойством, что если вход задачи имеет ответ «да», то существует полиномиальный алгоритм, проверя­ющий (доказывающий) этот факт. С этой целью допол­ним множество обычных операторов, из которых мы со­ставляли алгоритмы, одним особым. Пусть A = А1, А2, ..., Am — последовательность, элементами которой служат обычные операторы и один особый, запись ко­торого имеет вид B(l₁, l₂), l₁ ,l₂ €{1, 2, ..., т}. Пусть, далее, Q = q₁, q₂ ,..., q_p — такой список, что q_i = l₁ либо q_i = l₂ ( i = 1, р). После того как A и Q заданы, дей­ствие особого оператора B(l₁, l₂) определим так: в ре­зультате k-го(k≤p) выполнения этого оператора уп­равление передается оператору А_l1 если q_k = l₁ , и А_l2, если q_k = l₂, а при k > р вычисления прекращаются. Итак, последовательности операторов A и списку Q ставится в соответствии обычный (детерминированный) ал­горитм. Этот алгоритм будем обозначать через A_Q, что­бы подчеркнуть наличие двух компонент A и Q. Список Q будем при этом называть угадывающей последователь­ностью, а последовательность A — недетерминированным алгоритмом. Подчеркнем особо, что недетерминирован­ный алгоритм не является алгоритмом, а представляет собой чисто абстрактную конструкцию.

Будем говорить, что недетерминированный алгоритм A решает распознавательную задачу за полиномиальное время, если найдется такой полином р(п), что выпол­няется следующее условие: каждый вход длины п этой задачи имеет ответ «да» тогда и только тогда, когда для негр существует такая угадывающая последовательность Q, что алгоритм A_Q, будучи примененным к этому вхо­ду, останавливается, сообщив ответ «да», и время его работы не превосходит р(п). Заметим, что согласно это­му определению каждому входу с ответом «да» должен ставиться в соответствие свой алгоритм A_Q .От этого ал­горитма не требуется ничего иного, кроме правильной реакции на свой вход. Поведение алгоритма на всех дру­гих входах для нас безразлично.

Задача недетерминированно разрешима за полиноми­альное время, если существует недетерминированный ал­горитм, решающий ее за это время.

Определим теперь NP как класс всех распознаватель­ных задач, недетерминированно разрешимых за полино­миальное время.

Нетрудно видеть, что Р € NP. Действительно, полино­миальный алгоритм решения всякой задачи из Р можно превратить в полиномиальный алгоритм вида A_Q, доба­вив оператор B(l₁, l₂) так, чтобы он ни разу не сраба­тывал. При этом в качестве Q можно взять произволь­ную последовательность, например, состоящую из одного элемента. Класс NP чрезвычайно широк. Например, боль­шинству задач, встречающихся в предыдущих главах, можно «естественным» образом сопоставить распознава­тельные задачи. При этом окажется, что почти все они принадлежат NP.

В качестве примера доказательства принадлежно­сти задачи к NP рассмотрим задачу об изоморфном подграфе, которую здесь сформулируем в следую­щем виде.

Очевидно, что ограничение VG₁=VG2, которого нет в определении, приведенном в § 27, несущественно. Удобно рассматривать эту задачу в матричной постанов­ке. Пусть V ={1, 2, ..., п}, А₁ и А₂ — матрицы смеж­ности графов G₁ и G₂ соответственно. Обозначим через S матрицу подстановки s (см. § 6). Теперь задачу об изо­морфном подграфе можно сформулировать так: опреде­лить, существует ли такая матрица подстановки S, что все единицы матрицы SА₁S^-1 содержатся среди единиц матрицы А₂, т. е. что матрица (A₂ - SА₁S^-1) неотри­цательна.

Недетерминированный алгоритм A для решения этой задачи выглядит следующим образом. __________________________________

1. Выполнить пп. 2—4 для всех k = 1, п² и перейти к п. 5.

2.B(3,4).

3. t_k:=0.

4. t_k:=1

5. S_ij := t_i(n-1)+j для всех i, j = 1, п.

6. A= SА₁S^-1

7. Если матрица A₂ — А' неотрицательна, то конец и ответ «да». Иначе — конец.

Напомним, что S_ij — элемент матрицы S, занимающий позицию (i, j).

Покажем теперь, как выбирать угадывающую после­довательность Q. Рассмотрим произвольный вход задачи, имеющий ответ «да». Это — пара симметрических (0,1)-матриц А₁ и А₂, для которой существует такая матрица подстановки S, что A₂ - SА₁S^-1— неотрицательная мат­рица. Заменим в матрице S0на Зи1на4ив качестве Q возьмем последовательность элементов этой новой мат­рицы, выписанных по строкам.

Работа алгоритма A_Q состоит из двух этапов. На пер­вом этапе (пп. 1—5) с помощью Q строится матрица подстановки, обеспечивающая изоморфное вложение. Со­держанием второго этапа (пп. 6, 7) является проверка того, что матрица S обладает нужным свойством. Полиномиальность алгоритма A_Q очевидна.

Напомним, что частными случаями задачи об изо­морфном подграфе являются задачи об изоморфизме гра­фов, о существовании в графе гамильтонова цикла или клики заданного размера и ряд других. Таким образом, попутно установлена принадлежность всех этих задач к классу NP. Доказательство этого свойства для других графовых задач проводится, как правило, столь же про­сто. При этом работа алгоритма A_Q, так же как и в предыдущем случае, распадается на два этана: 1) по­строение некоторого варианта, 2) проверка того, что этот вариант подходящий. Например, в задаче о k-раскраске вершин графа такой алгоритм сначала припишет верши­нам графа нужные цвета, а затем проверит, что любые две вершины одного цвета не смежны.

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

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

Пусть существует полиномиальный алгоритм F, кото­рый, будучи примененным ко всякому входу I задачи A, строит некоторый вход F(I) задачи В. Если при этом вход I имеет ответ «да» тогда и только тогда, когда от­вет «да» имеет вход F(I), то говорят, что задача А по­линомиально сводится к задаче B, и пишут A∞В. По­скольку сводимостей, отличных от полиномиальной, мы не рассматриваем, то слово «полиномиально» в дальней­шем будем опускать и говорить просто «А сводится к В».

Нетрудно показать, что если задача А сводится к эадаче В и В € Р, то и А € Р. Действительно, пусть A — алгоритм решения задачи В и полиномы p₁(n), p₂(n) таковы, что O(p₁(n)) и О(р₂(п)) — сложности алгорит­мов F и A соответственно. Рассмотрим теперь алгоритм A' решения задачи А,состоящей из двух этапов. На первом этапе вход I задачи А преобразуется алгорит­мом F во вход F(I) задачи В. На втором этапе алгоритм A применяется ко входу F(I). Согласно определению F, алгоритм A сообщит ответ «да» тогда и только тогда, когда вход I имеет ответ «да», т. е. алгоритм A' дей­ствительно решает задачу А. Выясним теперь его слож­ность. Если длина I равна n, то F(I) будет построен за время О(p₁(п)), и его длина — О(p₁(п)). При этом алгоритм A, будучи примененным ко входу F(I), затра­тит время O(p₂(p₁(n))). Таким образом, сложность алго­ритма A' есть O(p₁(n) + p₂(p₁{n))). Поскольку супер­позиция и сумма полиномов также являются полинома­ми, то A' — полиномиальный алгоритм.

Точно так же можно показать, что из А ∞В и В ∞С следует А ∞ С.

Задачу А назовем NP-полной, если А € NP и любая задача из NP сводится к А.

Из этого определения и предыдущих рассмотрений сразу следует, что P = NP, если хотя бы одна МР-полная задача входит в Р.

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

Первой задачей, относительно которой было показано, что она является NP-полной, была задача о выполни­мости. Пусть х₁ , х₂ , х₃ ,…—булевы переменные, прини­мающие значения «истина» или «ложь», и х₁, х₂ , х₃ — их отрицания. Те и другие в совокупности называются литералами. Пусть символы V и ^ обозначают булевы операции дизъюнкции и конъюнкции соответственно. Формула u₁ V u₂ V ... V u_m называется элементарной дизъ­юнкцией, если u₁, u₂, ..., u_m — литералы. Пусть С₁ , С₂ ,..., С_р — элементарные дизъюнкции. Тогда выражение вида С₁ ^ С₂ ^ ... ^ С_р называется булевым выраже­нием в конъюнктивной нормальной форме. Булево выра­жение называется выполнимым, еесли входящим в него переменным можно так присвоить значения «истина» или «ложь», что значением выражения будет «истина». Не все выражения являются выполнимыми. Например, булево выражение вы­полнимо,

а выражение не выполнимо.

Задача о выполнимости (ВЫПОЛНИМОСТЬ) состоит в определении, является ли данное булево выражение в конъюнктивной нормаль­ной форме выполнимым.

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

Теорема (С. Кук, 1971 г.). Задача ВЫПОЛНИ­МОСТЬ является NP-полной.

В настоящее время известен значительный (и интен­сивно пополняющийся) список NP -полных задач. В этом списке находятся почти все задачи, получившие ранее репутацию трудных для алгоритмического решения. Ни­же приведены только те из них, с которыми мы сталки­вались в предыдущих главах. Некоторые NP -полные задачи.

КЛИКА: Даны граф G и натуральное число k. Опре­делить, содержит ли граф G клику мощности k.

НЕЗАВИСИМОСТЬ: Даны граф G и натуральное число k. Определить, содержит ли граф G независимое k-элементное множество вершин.

ИЗОМОРФНЫЙ ПОДГРАФ: Даны два графа G₁=(V,E₁) и G₂= (V,E₂). Определить, существует ли под­становка s: V-> V, для которой истинна импликация (uv € E₁)=>(s(u)s(v)€E₂).

ВЕРШИННОЕ ПОКРЫТИЕ: Даны граф G и нату­ральное число k. Определить, существует ли в графе G вершинное покрытие мощности не более k.

ДОМИНИРУЮЩЕЕ МНОЖЕСТВО: Даны граф G и натуральное число k. Определить, существует ли в гра­фе G доминирующее множество мощности не менее k.

ГАМИЛЬТОНОВ ЦИКЛ: Дан граф G. Определить, содержит ли граф G гамильтонов цикл.

ЯДРО: Дан ориентированный граф G. Определить, содержит ли граф G ядро.

ВЕРШИННАЯ (РЕБЕРНАЯ) РАСКРАСКА: Даны граф G и натуральное число k. Определить, существует ли правильная k-раскраска вершин (ребер) графа G.

Рассмотрим в качестве примера доказательство NP-полноты задачи КЛИКА. Пусть L_k — граф, у которого некоторые k вершин образуют клику, а остальные п — k — изолированные вершины. Ранее мы установили, что задача ИЗОМОРФНЫЙ ПОДГРАФ принадлежит NP. Если в этой задаче положить G₂ = G,где G— граф,фигурирующий в формулировке задачи КЛИКА, ав ка­честве G₁ выбрать граф L_k , то получим задачу КЛИКА. Следовательно, задача КЛИКА принадлежит NP.

Покажем теперь, что ВЫПОЛНИМОСТЬ ∞ КЛИКА. Пусть В = С₁ V С₂ V....V С_т — произвольное булево вы­ражение в конъюнктивной нормальной форме, { u₁, u₂, ..., u_m} — множество входящих в него литералов. Будем обозначать через С’₁ множество литералов, входящих в элементарную дизъюнкцию С_i

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

Пусть в графе G имеется клика размера k = т. Этой клике соответствует набор таких т вхождений u_i1 € С’₁ u_i2 €С’₂ , .., u_im € С’_m, что u_ii≠u_ii. Поэтому после при­своения всем u_{i j}(j=1,m) значения «истина» выраже­ние В также примет это значение, т. е. В — выполнимое выражение.

Наоборот, предположим, что В — выполнимое выра­жение. Пусть переменным присвоены значения «истина» или «ложь» так, что выражение В получило значение «истина». Тогда каждая элементарная дизъюнкция С₁ должна содержать литерал u_{i j} имеющий значение «исти­на». Ясно, что при этом u_{i а} ≠ u_{i t}. Следовательно, т вер­шин u_1i1 , u_{2 i2},…, u_{m Ii m} попарно смежны в графе G, т. е. образуют клику размера т. Таким образом, выражение В выполнимо тогда и только тогда, когда в графе G име­ется клика размера k = т. Легко видеть, что построение графа G по выражению В можно выполнить за время О(р(п)), где р(п)—полином, а п — длина записи выра­жения В (длина входа задачи ВЫПОЛНИМОСТЬ).

Имеется ряд задач, входящих в NP, для решения ко­торых до сих пор не найденополиномиальных алгоритмов и относительно которых неизвестно, являются ли они NP-полными. Наиболее заметной графовой задачей среди них является задача об изоморфизме графов.

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