36.2 Четыре возможных ситуации (имеется в виду, что все показанные на рисунке области непусты).

(а) Классы Р, NP и со - NP совпадают. (Большинство экспертов

(b)Класс NP замкнут относительно дополнения (NP=co-NP), но не совпадает с Р.

(c)Класс NP не замкнут относительно дополнения и в пересечении с co-NP даёт Р.

(с!) Класс NP не замкнут относительно дополнения; пересечение NP п со - NP больше, чем Р.

класс NP определялся в терминах так называемых недетерминированных вычислений (см. книгу Хопкрофта и Ульмана [104]).

Мы уже знаем одну задачу из класса NP - это задача HAM-CYCLE. Кроме того, всякая задача из Р принадлежит также и NP. Действительно, если есть полиномиальный алгоритм, распознающий язык, то легко построить проверяющий алгоритм для того же языка - проверяющий алгоритм может просто игнорировать свой второй аргумент (сертификат). Таким образом Р С NP.

В данное время неизвестно, совпадают ли классы Р и NP, но большинство специалистов полагает, что нет. Интуитивно класс Р можно представлять себе как класс задач, которые можно быстро решить, а класс NP - как класс задач, решение которых может быть быстро проверено. На практике решить самому задачу часто намного труднее, чем проверить уже готовое решение, особенно если время работы ограничено. По аналогии можно думать, что в классе NP имеются задачи, которые нельзя решить за полиномиальное время.

Есть и более серьёзные причины полагать, что Р ф NP - прежде всего это существование «NP-полных» задач (раздел 36.3).

Кроме проблемы Р = NP, остаются открытыми и многие другие вопросы о классе NP. Так, несмотря на огромные усилия исследователей, не известно, замкнут ли класс NP относительно дополнения, то есть верно ли, что из L £ NP следует L £ NP. Мы можем определить сложностной класс со - NP как множество языков L, для котрых L £ NP. Вопрос о замкнутости класса NP относительно дополнения можно переформулировать так: равны ли классы NP и co-NP?

Поскольку класс Р замкнут относительно дополнения (упр. 36.17), Р с NP п со - NP. В то же время остаётся неизвестным, верно ли равенство Р = NP п со - NP. На рис. 36.2 показаны четыре возможных ситуации.

Увы, наши знания о соотношении классов Р и NP далеко не полны (говоря прямо, мы вообще ничего не знаем). Но уже понятие NP-полноты является важным средством классификации задач; как мы

увидим, оно сводит вопрос о сложности данной задачи к общему (пусть и не решённому) вопросу о соотношении классов Р и NP.

Упражнения

36.2-1

Рассмотрим язык GRAPH-ISOMORPHISM={(Gi, G2) : графы G\ и G2 изоморфны}. Докажите, что данный язык принадлежит классу NP (постройте полиномиальный алгоритм, проверяющий этот язык).

36.2-2

Докажите, что неориентированный двудольный граф с нечётным числом вершин не гамильтонов. 36.2-3

Покажите, что если HAM-CYCLE лежит в Р, то за полиномиальное время можно не только проверить, существует ли гамильтонов цикл, но и найти его.

36.2-4

Докажите, что класс языков NP замкнут относительно объединения, пересечения, конкатенации и ★-операции Клини. 36.2-5

Докажите, что любой язык из NP распознается некоторым алгоритмом за время 2°(п )), где п - длина входа, а к - не зависящая от п константа.

36.2-6

Гамильтоновым путём в графе называется путь, котрый проходит через каждую вершину графа ровно один раз. Докажите, что язык НАМ-РАТН={(С, и, v) : в графе G существует гамильтонов принадлежит NP.

36.2-7

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

36.2-8

Пусть Lp - булева формула, построенная из булевых переменных Х\ , х2}• • • ,

хп с помощью операций отрицания (->), конъюнкций (И, Л), дизъюнкций (ИЛИ, V) и скобок. Формула Lp называется тавтологией (tautology), если она истинна для всех значений переменных. Определим язык TAUTOLOGY, состоящий из всех тавтологий. Покажите, что TAUTOLOGY принадлежит co-NP. 36.2-9

Докажите, что Р С со - NP 36.2-10

Докажите, что если NP ф со - NP, то Р ф NP. 36.2-11

Пусть G - связный неориентированный граф, имеющий не меньше трёх вершин. Рассмотрим граф С3, который получится, если со-

единить ребром каждую пару вершин графа G, которые соединены в G путём длины не больше 3. Докажите, что граф G3 гамильтонов. (Указание: постройте покрывающее дерево графа G и примените математическую индукцию.)

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

В частности, задача НАМ-РАТН (о гамильтоновом цикле) является NP-полной. Таким образом, если научиться решать её за полиномиальное время, то и для всех задач класса NP существовали бы полиномиальные алгоритмы. Переформулировка: NP \ Р непусто, то HAM-PATH G NP \ Р.

Неформально говоря, NP-полные языки являются самыми «трудными» в классе NP. При этом трудность языков можно сравнивать, сводя один язык к другому. В этом разделе мы даём определение сводимости, затем определяем класс NP-полных языков и устанавливаем полноту одного конкретного языка, CIRCUIT-SAT. В разделе 36.5 мы используем метод сведения для доказательства NP-полноты многих других задач.

Сводимость

Говоря неформально, задача Q сводится к задаче Q, если задачу Q можно решить для любого входа, считая известным решение задачи Q для какого-то другого входа. Например, задача решения линейного уравнения сводится к задаче решения квадратного уравнения (линейное уравнение можно превратить в квадратное, добавив фиктивный старший член). Если задача Q сводится к задаче Q, то любой алгоритм, решающий Q, можно использовать для решения задачи Q, то есть Q «не труднее» Q.

Дадим формальное определение. Говорят, что язык L\ сводится за полиномиальное время (is polynomial-time reducible) к языку L2 (запись: L\ L2), если существует такая функция / : {0,1}* -> {0,1}*, вычислимая за полиномиальное время, что для любого х £

Функцию / называют сводящей функцией (reduction function), а полиномиальный алгоритм F, вычисляющий функцию / - сводя-

36.3. NP-полнота и сводимость

{0,1}*