нии обычных команд или перескакивая в другое место программы в условных операторах и циклах).

Текущее состояние программы, определяющее дальнейший ход её исполнения, записано в каждый момент в памяти (мы включаем в это понятие регистры процессора, счётчик команд и т.п.). Каждое состояние памяти компьютера будем называть конфигурацией (configuration). Выполнение инструкций может рассматриваться как последовательное преобразование текущей конфигурации в следующую за ней в соответствии с некоторыми правилами. Эти правила определяются электроникой компьютера и могут быть представлены в виде схемы из функциональных элементов (если конфигурация представляется набором п битов, то эта схема имеет п входов и п выходов). В доказательстве следующей леммы мы будем обозначать эту схему через М.

Лемма 36.6

Задача CURCUIT-SAT является NP-трудной. Доказательство

Пусть L - произвольный язык из класса NP. Мы построим функцию /, которая будет отображать каждое двоичное слово в схему С = /(ж), для которой ж G L равносильно С G CIRCUIT - SAT. (Функция / будет вычисляться полиномиальным алгоритмом.)

Поскольку L G NP, существует алгоритм А, проверяющий данный язык за полиномиальное время. Мы используем этот алгоритм для построения сводящего алгоритма F. Пусть Т(п) - наибольшее время работы алгоритма А на входах длины п (напомним, что мы называем входом первый аргумент алгоритма А; второй называется сертификатом). Выберем такое число /г, что Т(п) = 0(пк) и длина сертификатов для входов длины п тоже есть 0(пк). (Время работы алгоритма полиномиально зависит от общей длины условия и сертификата. Но поскольку длина сертификата ограничена полиномом от длины условия, время работы алгоритма также ограничено полиномом от п.)

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

Начальное состояние памяти компьютера образует конфигурацию со. Затем каждая конфигурация сг- преобразуется в следующую конфигурацию c8+i, причём это преобразование выполняется с помощью схемы из функциональных элементов М, реализованной в электронике компьютера. В конце работы алгоритм получает ответ (ноль или единицу). Будем считать, что этот ответ записывается в определённое место памяти. После получения ответа программа останавливается, и состояние памяти в дальнейшем не изменяется. Следовательно, если алгоритм делает не более Т(п)

переводы надписей:

input bits - сертификат aux machine state - регистры процессора working storage - рабочая память 0/1 output - выходной бит

36.7 Последовательность конфигураций, соответствующая работе алгоритма А для входа ж и сертификата у. Каждая конфигурация соответствует состоянию вычисления в какой-то момент времени и включает в себя (помимо А, х н у) также значение счётчика команд (PC), а также содержимое регистров процессора и рабочей памяти. Каждая конфигурация переводится в следующую с помощью схемы М из функциональных элементов. Выходной бит записан в выделенном месте рабочей памяти.

шагов, результат работы алгоритма находится в фиксированном бите конфигурации ctny

Таким образом, можно построить схему, которая последовательно вычисляет конфигурации с\, с2, , су(лг). Эта схема состоит из последовательно соединённых Т(п) копий схемы М. Выход г-ой копии схемы М будет конфигурацией сг-. Выходными значениями схемы будут биты конфигурации cjny Описанную схему назовем С.

Вспомним, что должен делать сводящий алгоритм F. Получив входное слово ж, он должен построить схему С = /(ж), которая выполнима, если и только если существует такой сертификат у, что А(х,у) = 1. Для этого найдём длину п слова ж и построим схему С описанным способом. Входом схемы С будет начальная конфигурация вычисления А(х,у), а выходом - конфигурация cjny

Затем полученную схему С следует немного преобразовать. Во-первых, нужно установить значения входных переменных, соответствующих программе А, начальному положению счетчика команд, входу ж, исходному состоянию служебной информации и рабочей части памяти. (Для этого мы соединяем соответствующие входы схемы с постоянными сигналами 0 или 1.) Неопределёнными остаются только те входные переменные, которые отвечают за значение сертификата у. Во-вторых, игнорируются все выходы схемы С, кроме одного - того бита конфигурации стпу в котором хранится результат работы алгоритма А. Новая, преобразованная схема и есть нужная нам схема С. Сводящий алгоритм, получив вход ж, строит схему С и выдаёт её (точнее, её представление в виде строки битов).

Остается доказать, что сводящий алгоритм обладает двумя необходимыми свойствами. Во-первых, нужно показать, что F корректно вычисляет сводящую функцию /. Это значит, что схема С выполнима тогда и только тогда, когда существует сертификат у, для которого А(х,у) = 1. Во-вторых, нужно показать, что алгоритм F работает полиномиальное время.

Докажем корректность алгоритма F. Пусть существует сертификат у длины 0(пк), для которого А(х,у) = 1. Подставим биты сертификата у во входные переменные схемы С. Тогда выход схемы С (у) будет равен А(х,у) = 1. Таким образом, если существует сертификат, то схема С = f(x) выполнима. Наоборот, если схема С выполнима, то для некоторого набора у значений входных переменных имеем С (у) = 1, и потому А(х,у) = 1. Корректность алгоритма F доказана.

Осталось заметить, что размер схемы С и время работы сводящего алгоритма полиномиально зависят от размера входа п = \х\. Прежде всего заметим, что каждая конфигурация содержит полиномиальное число битов. Действительно, длина программы А фиксирована и не зависит от входа, длина входа х равна п, а длина сертификата у полиномиально зависит от п. Поскольку алгоритм А делает только полиномиальное число шагов, размер используемой им памяти тоже полиномиален. (Мы считаем, что не только число фактически использованных ячеек памяти, но и общее число ячеек памяти полиномиально. На самом деле это ограничение несущественно, см. упр. 36.3-4.) Таким образом, и число уровней на рис. 36.7, и размер каждого уровня полиномиальны; конструкция схемы также регулярна и построение её за полиномиальное время не составляет труда.

Итак, мы доказали, что язык CIRCUIT-SAT лежит в классе NP и что любой язык из NP к нему сводится, то есть что задача CIRCUIT-SAT является NP-полной.

Теорема 36.7

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

Упражнения

36.3-1

Покажите, что отношение транзитивно, то есть что из L\ р L2 и L2 р L3 следует Lt Р L3. 36.3-2

Докажите, что L р L, если и только если L р L 36.3-3

Проверьте, что в доказательстве леммы 36.5 в качестве сертификата можно взять значения на всех проводах (входных, выходных и внутренних) схемы.

36.3-4

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

36.3-5

Язык L называется полным в классе языков С относительно полиномиальной сводимости, если L £ С и V L для любого V £ С.