Докажите, что в классе Р все языки (кроме 0 и {0,1}*) полны относительно полиномиальной сводимости. 36.3-6

Покажите, что язык L полон в классе NP тогда и только тогда, когда язык L полон в со - NP. 36.3-7

Сводящий алгоритм F (лемма 36.6) строит схему С = /(ж), используя информацию об ж, А и к. Профессор заметил, что алгоритм F получает в качестве аргумента только ж, однако ни А, ни к ему не даны. (Поскольку язык L принадлежит NP, можно утверждать, что требуемые А и к существуют, но каковы они, мы не знаем.) На этом основании профессор делает вывод, что алгоритм F построить нельзя, и что язык CIRCUIT-SAT не обязан принадлежать NP. Объясните, в чём ошибка профессора.

Доказательства NP-полноты.

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

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

Лемма 36.8

Если для языка L найдется язык V £ CNP, для которого V L, то язык L NP-труден. Если, кроме того, L £ NP, то С £ CNP. Доказательство

Поскольку V £ CNP, любой язык L" из класса NP сводится к V. По условию V р L, поэтому по свойству транзитивности (упр. 36.3-1) L" L. Таким образом, язык L является NP-трудным. Если теперь L £ NP, то С £ CNP.

Другими словами, нам не надо доказывать, что любой NP-язык сводится к интересующему нас - достаточно проверить это для одного NP-полного языка. Получаем такую схему доказательства NP-полноты языка L.

1.Доказываем, что L £ NP.

2.Выбираем какой-либо известный NP-полный язык V.

3.Строим алгоритм, вычисляющий функцию /, которая отображает входы задачи V во входы задачи L.

4.Доказываем, что функция / сводит V к L, то есть что ж £ С тогда и только тогда, когда /(ж) £ L.

5.Доказываем, что вычисляющий функцию / алгоритм работает полиномиальное время.

Можно сказать и так: мы уже пробили брешь в стене, установив

(36.2)

NP-полноту одного языка, и теперь можем использовать это для доказательства NP-полноты других языков. Эти языки также можно использовать как эталонные при доказательстве NP-полноты, так что чем больше наша коллекция NP-полных языков, тем легче доказывать NP-полноту новых. Выполнимость формул

Мы докажем NP-полноту задачи о выполнимости пропозициональных формул. (Именно для этой задачи впервые была доказана NP-полнота.) Вот как она формулируется.

Пропозициональные формулы составлены из

1.булевых переменных х\, х2,... ;

2.булевских операций (пропозициональных связок) Л (конъюнкция, AND, И), V (дизъюнкция, OR, ИЛИ), -. (отрицание, НЕ, NOT), => (импликация, следование), <ФФ (эквивалентность, если и только если);

3.скобок.

Так же как и для булевых схем, набором значений (truth assignment) для пропозицональной формулы Lp будем называть набор значений переменных, входящих в эту формулу. Выполняющим набором (satisfying assignment) мы называем набор значений, на котором формула принимает значение 1 (истинна). Формула называется выполнимой (satisfiable), если для неё существует выполняющий набор. Задача о выполнимости формулы (formula satisfiability problem) состоит в проверке, является ли заданная (пропозициональная) формула выполнимой. Другими словами,

SAT = {(lp) : Lp - выполнимая булева формула}.

Например, формула

Lp = ({xi => х2) V -((-1ж1 <ФФ х3) V х4)) А -1ж2

имеет выполняющий набор (х\ = 0, х2 = 0, х3 = 1, х4 = 1), так как

Lp = ((0 => 0) V -.((-.0 1) V 1)) Л -.0 = (1V-i(1V1))A1 = (1V0)A1 = 1,

и, следовательно, данная формула Lp принадлежит SAT.

Выполнимость формулы можно проверить, перебрав все наборы значений переменных. Однако этот переборный алгоритм не является полиномиальным (для формулы с п переменными есть 2п вариантов). Как показывает следующая теорема, задача SAT является NP-полной и потому для неё вряд ли существует полиномиальный алгоритм.

Теорема 36.9

36.8

Сведение выполнимости схемы к выполнимости формулы. Для каждого провода схемы заводим переменную; формула представляет собой конъюнкцию утверждений о поведении каждого элемента.

Задача о выполнимости формулы NP-полна. Доказательство

Прежде всего убедимся, что SAT £ NP. В самом деле, сертификатом является выполняющий набор, а проверяющий алгоритм подставляет значения из этого набора на место переменных и вычисляет значение формулы.

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

Можно построить формулу, которая вычисляет ту же функцию, что и заданная схема. Это делается просто: двигаясь от входов схемы к выходу, мы на каждом проводе пишем формулу, ему соответствующую (например, выходу элемента И соответствует формула <~р А ф, где <р и ф - формулы, соответствующие её входам).

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

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

Формула, которую строит сводящий алгоритм, есть конъюнкция переменной, соответствующей выходу схемы, и утверждений о корректности работы всех функциональных элементов. Например, схеме на рисунке 36.8 будет поставлена в соответствие формула

ip = жюЛ(ж4 -1Ж3)

Л(ж5 <5 -.(xi V ж2)) Л(ж6 -1Ж4) Л(Ж7 -Л ж2 Л ж3)) Л(ж8 -.(ж5 V ж6)) Л(ж9 <> ->(хе V Ж7))

Л(жю <5 ->(Ж7 Л Ж8 Л Жд))

Это построение, как легко видеть, приводит к схеме полиномиального размера и выполняется за полиномиальное время.

Почему схема С выполнима тогда и только тогда, когда выполнима построенная формула р>1 Пусть схема С имеет выполняющий