щим алгоритмом (reduction algorithm).

Рисунок 36.3 иллюстрирует определение сводимости языка L\ к языку L2 за полиномиальное время. Каждый язык есть подмножество множества {0,1}*. Сводящая функция переводит любое слово х £ L\ в слова f(x) £ L2, а слово х L\ - в слово f(x) L2. Поэтому, если мы узнаем, принадлежит ли слово f(x) языку L2, мы тем самым получим ответ на вопрос о принадлежности слова х языку L\.

Лемма 36.3

Если язык L\ С {0,1}* сводится за полиномиальное время к языку L2 С {0,1}*, то то из L2 £ Р следует L\ £ Р.

Доказательство Пусть А2 - полиномиальный алгоритм, распознающий язык L2, a F - полиномиальный алгоритм, сводящий язык L\ к языку L2. Построим алгоритм А\, который будет за полиномиальное время разрешать язык L\.

Рисунок 36.4 иллюстрирует построение. Получив вход х £ {0,1}*, алгоритм А\ (с помощью алгоритма F) получает f(x) и с помощью алгоритма А2 проверяет, принадлежит ли слово f(x) языку L2. Результат работы алгоритма А2 на слове f(x) и выдается алгоритмом А\ в качестве ответа.

Определение (36.1) гарантирует, что алгоритм А\ даёт правильный ответ; он полиномиален, поскольку полиномиальны алгоритмы F и Аг (упр. 36.1-6).

NP-полнота

Понятие сводимости позволяет придать точный смысл утверждению о том, что один язык не менее труден, чем другой (с точностью до полинома). Запись L\ L2 можно интерпретировать так: сложность языка L\ не более чем полиномиально превосходит сложность языка L2. Наиболее трудны в этом смысле NP-полные задачи.

Язык L С {0,1}* называется NP-полным (NP-complete), если

1.L £ NP.

2.V Р L для любого V £ NP

Класс NP-полных языков будем обозначать NPC. Языки, которые обладают свойством 2 (но не обязательно обладают свойством 1), называют NP-трудными (NP-hard)

Основное свойство NP-полных языков состоит в следующем:

Теорема 36.4

Если некоторая NP-полная задача разрешима за полиномиальное время, то Р = NP.

Если в классе NP существует задача, не разрешимая за полиномиальное время, то все NP-полные задачи таковы.

Доказательство

Пусть L - NP-полный язык, который одновременно оказался разрешимым за полиномиальное время (L £ Р и L £ NPC). Тогда для любого V £ NP по свойству 2 определения NP-полного язы-

36.5

Предполагаемое соотношение между классами P. NP и NPC. Классы Р и NPC содержатся в NP (что очевидно), и, можно полагать, не пересекаются и не покрывают всего NP.

ВНИМАНИЕ: внутри треугольников с кружочками надо написать НЕ, внутри гнутых треугольников - ИЛИ, внутри кривых прямоугольников - И.

Два набора входных данных для задачи CIRCUIT-SAT. (а) Набор входных значений (х\ = 1,х2 = 1,жз = 0) даёт значение 1 на выходе, так что эта схема выполнима. (Ь) Для этой схемы никакой набор входных значений не приводит к единице на выходе, так что эта схема не выполнима.

ка имеем V L. Следовательно, V £ Р (лемма 36.3), и первое утверждение теоремы доказано.

Второе утверждение теоремы является переформулировкой первого.

Таким образом, гипотеза Р ф NP означает, что NP-полные задачи не могут быть решены за полиномиальное время. Большинство экспертов полагает, что это действительно так; предполагаемое соотношение между классами Р, NP и CNP показано на рис. 36.5.

Конечно, мы не можем быть уверены, что однажды кто-нибудь не предъявит полиномиальный алгоритм для решения NP-полной задачи и не докажет тем самым, что Р = NP. Но пока что этого никому не удалось, и потому доказательство NP-полноты некоторой задачи является убедительным аргументом в пользу того, что она является практически неразрешимой.

Задача о выполнимости для схем

Как мы уже говорили, мы начнём с одной конкретной задачи; установив её NP-полноту, можно доказывать NP-полноту других задач методом сведения. В качестве такой задачи мы рассмотрим задачу о выполнимости для схем (circuit-satisfyability problem, или CIRCUIT-SAT). К сожалению, подробное доказательство NP-полноты этой задачи требует рассмотрения технических деталей, выходящего за рамки данной книги. Поэтому мы ограничимся неформальным наброском доказательства, полагая, что читатель имеет представление о схемах из функциональных элементов (см. гл. 29).

На рисунке 36.6 показаны две схемы из функциональных элементов. Обе имеют по три входа и по одному выходу.

Будем рассматривать наборы значений булевых переменных, соответствующих входам схем (truth assignments). Схема из функциональных элементов с одним выходом называется выполнимой (satisfiable), если существует выполняющий набор (satisfying assignment), то есть такой набор значений входов, при котором на выхо-

де схемы появляется единица. Например, схема рис. 36.6(a) имеет выполняющий набор (х\ = 1, х2 = 1, жз = 0) и потому является выполнимой. В то же время никакие значения переменных ж1,ж2,жз для схемы рис. 36.6(6) не приводят к появлению 1 на выходе. Следовательно, эта схема невыполнима.

Задача о выполнимости схемы (circuit-satisfiability problem) требует выяснить, «является ли данная схема, составленная из элементов И. ИЛИ и НЕ, выполнимой». Конечно, нужно договориться о способе представления булевых схем с помощью строк битов - это делается естественным образом (подобно тому, как это делается для графов); при этом размер полученной строки битов не более чем полиномиально зависит от размера схемы. Зафиксировав такое представление, рассмотрим язык

CIRCUIT-SAT = {(С) : С - выполнимая схема из функциональных элементов}

Задачу о выполнимости можно сформулировать так: можно ли данную схему заменить на эквивалентную, в которой выход соединён напрямую с нулевым проводом.

Разумеется, можно узнать, выполнима ли данная схема, перебрав все возможные комбинации значений входов. К сожалению, их много: для схемы с к входами придется перебрать 2к наборов - время работы такого переборного алгоритма не ограничено полиномом (от к, или, что то же, от размера схемы). Как мы уже отмечали, большинство специалистов уверены, что что задача о выполнимости схемы не может быть решена полиномиальным алгоритмом (поскольку NP-полна).

Для начала убедимся, что задача CIRCUIT-SAT принадлежит классу NP.

Лемма 36.5

Задача CIRCUIT-SAT принадлежит классу NP. Доказательство

Сертификатом является набор входных значений, при которых выходное значение равно 1 - ясно, что этот факт легко проверить за полиномиальное время.

Для доказательства NP-полноты задачи CIRCUIT-SAT нам осталось доказать, что данная задача NP-трудна, то есть что любая задача из класса NP сводится к задаче CIRCUIT-SAT за полиномиальное время. Полное доказательство этого утверждения довольно громоздко, так что мы дадим лишь набросок доказательства.

Коротко напомним, как устроен компьютер. Программа хранится в памяти компьютера в виде последовательности инструкций (команд). Инструкции содержат код операции, которую нужно выполнить, адреса аргументов (операндов) команды и адрес, по которому следует записать результат операции. В специальном месте памяти, которое называется счётчиком команд (program counter), хранится адрес текущей команды. Этот адрес в процессе выполнения программы меняется (постепенно увеличиваясь при выполне-