РАЗРЕШИМЫЕ И НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ

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

Начнем с внесения изменений в вычислительную модель. Будем считать, что каждая ячейка абстрактной вычислительной машины может содержать только 0 или 1, и целые числа рассматриваются в двоичной системе счисления. В соответствии с этим всякое целое число a ≠ 0, 1 займет ]log |a|[ ячеек машинной памяти (]x[ – наименьшее целое, не меньшее чем x). Рациональное число, не являющееся целым, будем рассматривать в виде несократимой дроби и представлять в машине как упорядоченную пару целых чисел – числитель и знаменатель этой дроби. Время выполнения каждой элементарной операции примем равным сумме длин записей ее операндов в двоичной системе счисления.

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

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

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

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

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

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

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

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

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

Даны два графа G₁ и G₂, причем VG₁ = VG₂ = V. Установить, существует ли такая подстановка s: V → V, для которой истинна импликация

(uv Î EG₁) Þ (s(u)s(v)Î EG₂).

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

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

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

2. B(3,4).

3. t_k=0.

4.t_k=1.

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

6. А':=SA₁S^-1.

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

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

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

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

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

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

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

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

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

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