G = (V, Е) - неориентированный граф, u,v £ V, k О - целое число, и существует простой путьиз и в v, длины не менее Покажите, что задача оптимизации LONGEST-PATH-LENGTH может быть решена за полиномиальное время в том и только том случае, если задача разрешения LONGEST-PATH принадлежит классу Р. 36.1-2

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

36.1-3

Рассмотрите два представления для графа - с помощью матрицы инцидентности (закодированной последовательностью битов) и с помощью списков рёбер (также надлежащим образом закодированных). Объясните, почему два данных представления полиномиально связаны.

36.1-4

Является ли алгоритм динамического программирования для 0-1-задачи о рюкзаке из упражнения 17.2-2 полиномиальным? Объясните свой ответ.

36.1-5

Предположим, что некоторый язык L допускается за полиномиальное время некоторым алгоритмов. Может ли этот алгоритм работать более чем полиномиальное время на словах, не принадлежащих L1 (Сравните свой ответ с утверждением теоремы 36.2.)

36.1-6

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

36.1-7

Покажите, что класс Р как множество языков замкнут относительно объединения, пересечения, дополнения, конкатенации и операции Клини. Это значит, что из L\, L2 £ Р следует Е\ L)L2 £ Р и т.д.

36.2. Проверка принадлежности языку и класс NP

В предыдущем разделе мы рассматривали задачу разрешения PATH (выяснить, есть ли в данном графе G между данными двумя вершинами и и v путь длины не более к). Эта задача оказалась полиномиальной (и решается с помощью алгоритма поиска в ширину). Представим себе, однако, что мы ничего не знаем про поиск

36.1 (а) Додекаэдр (вид из точки, расположенной недалеко от центра одной из граней); серые рёбра образуют гамильтонов цикл. (Ь) Двудольный граф с нечётным числом вершин - такой граф не гамильтонов.

в ширину. Тогда задача PATH будет для нас трудной: видя граф G, вершины и и v и знаю число к, мы не будем знать, есть ли искомый путь, пока нам кто-нибудь его не покажет. Но если нам его покажут, то мы можем без труда проверить, что путь этот - искомый.

Именно такая ситуация имеет место для задач из класса NP, о которых мы будем говорить в этом разделе. Гамильтонов цикл

Задача поиска гамильтонова цикла в графе изучается уже более ста лет. Бонди и Мёрти [131] цитируют письмо Гамильтона (W.R.Hamilton), в котором описана такая игра: первый игрок отмечает в додекаэдре (рис. 26.1(a)) путь из пяти идущих друг за другом вершин, а второй игрок должен дополнить этот путь до простого цикла, проходящего через все вершины додекаэдра.

Вообще гамильтоновым циклом (hamiltonian cycle) в неориентированном графе G = (V, Е) называется простой цикл, который проходит через все вершины графа. Графы, в которых есть гамильтонов цикл, называют гамильтоновыми (hamiltonian graph)

Додекаэдр (проекция которого изображена на рис. 35.1(a)) - гамильтонов граф; серым цветом показан один из гамильтоновых циклов. Не все графы гамильтоновы: на рис. 36.1(b) показан двудольный граф с нечётным числом вершин; легко видеть (упр. 36.22), что такой граф не может иметь гамильтонова цикла.

Задача о гамильтоновом цикле (hamiltonian path problem) состоит выяснении, имеет ли данный граф G гамильтонов цикл. Формально говоря,

HAM-CYCLE = {(G) : G - гамильтонов граф}

Как решать такую задачу? Можно перебрать все перестановки вершин данного графа и проверить, является ли хотя бы одна из них гамильтоновым циклом. Оценим время работы такого алгоритма. Если мы используем представление графа с помощью матрицы инцидентности, то число вершин то в графе будет Q(y/n), где п = (G) - длина представления графа G. Имеется то! различных перестановок вершин графа, и время работы алгоритма равно Г2(то!) = Q(y/n\) = Q{2), то есть не является полиномиальным. Таким образом, наивный алгоритм не даёт эффективного решения задачи. На самом деле, как мы покажем в разделе 36.1, задача о гамильтоновом цикле является NP-полной, и потому можно предполагать, что полиномиального алгоритма для неё вообще не существует.

Проверка принадлежности языку

Пусть вы заключили пари с приятелем, который утверждает, что (нарисованный перед вами на доске) граф является гамиль-тоновым. При этом вы не можете быстро проверить, так это или нет. Тем не менее приятель может выиграть пари, если каким-то образом отгадает гамильтонов цикл и предъявит его вам: проверка того, что данный цикл является гамильтоновым, проста. Нужно лишь проверить, что предъявленный цикл проходит через все вершины графа, и что он действительно идёт по рёбрам. Итак, доказательство существования гамильтонова цикла в графе (состоящее в предъявлении гамильтонова пути) можно проверить за полиномиальное время.

Назовем проверяющим алгоритмом (verification algorithm) алгоритм А с двумя аргументами; первый аргумент мы будем называть (как и раньше) входной строкой, а второй - сертификатом (certificatie). Мы говорим, что алгоритм А с двумя аргументами допускает вход ж (A verifies an input string ж), если существует сертификат у, для которого А(х,у) = 1. Языком, проверяемым алгоритмом A (language verified by А), мы назовём язык

L = {ж £ {0,1}* : существует у £ {0,1}*, для которогоА(ж, у) = 1}.

Другими словами, алгоритм А проверяет язык L, если для любой строки ж £ L найдется сертификат у, с помощью которого А может проверить принадлежность ж к языку L, а для ж L такого сертификата нет. Например, в задаче HAM-CYCLE сертификатом была последовательность вершин, образующая гамильтонов цикл. Сложностной класс NP

Сложностной класс NP (complexity class NP) - это класс языков, для которых существуют проверяющие алгоритмы, работающие полиномиальное время, причём длина сертификата также ограничена некоторым полиномом. Более точно, язык L принадлежит классу NP, если существует такой полиномиальный алгоритм А с двумя аргументами и такая многочлен р(х) с целыми коэффициентами, что

L = {ж £ {0,1}* : существует сертификат у, для которого \у\ р(ж) и А(х, у) = 1}

В этом случае мы говорим, что алгоритм А проверяет язык L за полиномиальное время (A verifies language L in polynomial time). Заметим, что, формально говоря, из этого не следует, что А проверяет язык L в смысле ранее данного определения, так как для ж L могут существовать длинные сертификаты, которые отбрасываются при новом определении, но препятствуют старому.

Несколько слов о названии: сокращение NP происходит от английских слов Nondeterministic Polynomial (time), что переводится как недетерминированное полиномиальное время. Первоначально