Материал: Дискретная математика. учебное пособие. Собенина О.В

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

Определим теперь 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  С следует А  С.

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

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

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

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

(x₁ V x₂) Λ ( V x₃) Λ ( V )

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

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

Теорема 5.1(С. Кук, 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.

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

Поставим в соответствие выражению В граф G по следующему правилу:

VG={v_ij : u_i  С'_i},

EG = {v_ij v_kl : u_i  _i , j  i }.

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

Пусть в графе G имеется клика размера k = т. Этой клике соответствует набор таких т вхождений u_i  C’₁, и_i С’₂, ..., u_i C’_m, что u_i  _i . Поэтому после при­своения всем u_i (j= ) значения «истина» выраже­ние В также примет это значение, т. е. В – выполнимое выражение.

Наоборот, предположим, что В – выполнимое выра­жение. Пусть переменным присвоены значения «истина» или «ложь» так, что выражение В получило значение «истина». Тогда каждая элементарная дизъюнкция C_l должна содержать литерал u_i , имеющий значение «исти­на». Ясно, что при этом u_i  _i .Следовательно, т вер­шин v_1i , v_2i , …, v_mi попарно смежны в графе G, т. е. образуют клику размера т. Таким образом, выражение В выполнимо тогда и только тогда, когда в графе G име­ется клика размера k=т. Легко видеть, что построение графа G по выражению В можно выполнить за время O (р(п)), где р(п) – полином, а п – длина записи выра­жения В (длина входа задачи ВЫПОЛНИМОСТЬ).

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

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

Теория NP-полноты, помимо теоретического, представ­ляет и чисто практический интерес. Доказав, что задача NP-трудна, разработчик алгоритмов получает достаточ­ные основания, чтобы отказаться от поиска эффектив­ного и точного алгоритма. Дальнейшие его усилия могут быть направлены, например, на получение приближен­ного решения, либо на получение решения в типичном случае (в большинстве случаев).

Заключение

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

Библиографический список

1. Емеличев В.А. Лекции по теории графов / В.А. Емеличев, О.И. Мельников. М.: Наука, 1990. – 384 с.

2. Кристофидес Н. Теория графов: алгоритмический подход / Н. Кристофидес. М.: Мир, 1978. – 432 с.

3. Свами М. Графы, сети и алгоритмы / М. Свами, К. Тхуласираман. М.: Мир, 1974. – 520 с.

4. Судоплатов С.В. Элементы дискретной математики: учебник / С.В. Судоплатов, Е.В. Овчинникова. М.: ИНФРА-М, 2002. – 280 с.

5. Леденева Т.М.Специальные главы математики. Дискретная математика: учеб. пособие / Т.М. Леденева. Воронеж: ВГТУ, 1997. – 130 с.

6. Новиков Ф.А. Дискретная математика для программистов / Ф.А. Новиков. СПб.: Питер, 2004. – 364 с.

7. Тишин В.В. Дискретная математика в примерах и задачах / В.В. Тишин. СПб.: БХВ-Петербург. 2008. – 352 с.

8. Гаврилов Г.П. Задачи и упражнения по дискретной математике: учеб. пособие / Г.П. Гаврилов, А.А. Сапоженко. – 3-е изд., перераб. М.: ФИЗМАТЛИТ, 2005. – 416 с.

9. Лавров И.А. Задачи по теории множеств, математической логике и теории алгоритмов / И.А. Лавров, Л.Л. Максимова. М.: ФИЗМАТЛИТ, 2004. – 256 с.

10. Кузнецов О.П. Дискретная математика для инженера / О.П. Кузнецов. СП.: Лань, 2005. - 400 с.

Оглавление