10.4. NP-ПОЛНОТА ЗАДАЧИ ВЫПОЛНИМОСТИ

Можно показать, что задача, а точнее ее представление в виде языка -полна, доказав, что принадлежит и всякий язык из полиномиально трансформируем в Благодаря "силе" недетерминизма принадлежность данной задачи классу обычно доказывается легко. Примеры 10.3 и 10.4 служат типичными иллюстрациями этого шага. Трудности вызывает доказательство того, что всякая задача из полиномиально трансформируема в данную задачу. Однако, раз уж установлена NP-полнота некоторой задачи можно доказать NP-полноту новой задачи показав, что принадлежит и задача полиномиально трансформируема в

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

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

Определения. Пусть неориентированный граф.

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

2. Гамильтоновым циклом называется цикл в графе содержащий все узлы из

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

Для представления важных NP-полных задач об ориентированных графах нам понадобятся следующие определения.

Определения. Пусть ориентированный граф.

1. Множеством узлов, разрезающих циклы, называется такое подмножество что каждый цикл в содержит узел из

2. Множеством ребер, разрезающих циклы, называется такое подмножество что каждый цикл в содержит ребро из

3. Ориентированным гамильтоновым циклом называется цикл в графе содержащий все узлы из

Теорема 10.2. Следующие задачи принадлежат классу

1. (Выполнимость) Выполнима ли данная булева формула?

2. (Клика) Содержит ли данный неориентированный граф -клику?

3. (Узельное покрытие) Имеет ли данный неориентированный граф узельное покрытие размера

4. (Гамильтонов цикл) Имеет ли данный неориентированный граф гамильтонов цикл?

5. (Раскрашиваемость) Является ли данный неориентированный граф -раскрашиваемым?

6. (Множество узлов, разрезающих циклы) Имеет ли данный ориентированный граф -элементное множество узлов, разрезающих циклы?

7. (Множество ребер, разрезающих циклы) Имеет ли данный ориентированный граф -элементное множество ребер, разрезающих циклы?

8. (Ориентированный гамильтонов цикл) Имеет ли данный ориентированный граф ориентированный гамильтонов цикл?

9. (Покрытие множествами) Существует ли для данного

семейства множеств такое подсемейство из множеств что

10. (Точное покрытие) Существует ли для данного семейства множеств подсемейство попарно непересекающихся множеств, являющееся покрытием?

Доказательство. Принадлежность задач 1 и 2 классу показана соответственно в примерах 10.4 и 10.3. Аналогично для каждой из остальных задач надо построить недетерминированную машину Тьюринга (или, если читателю угодно, недетерминированную полиномиальной сложности, которая "угадывает" решение и проверяет, что это действительно решение. Детали оставляем в качестве упражнения.

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

Теорема 10.3. Задача выполнимости булевой формулы NP-полна.

Доказательство. Мы уже знаем, что задача выполнимости принадлежит Осталось показать, что всякий язык из полиномиально трансформируем в задачу выполнимости. Пусть недетерминированная машина Тьюринга, распознающая за полиномиальное время, и пусть на ее вход подана цепочка Из можно построить булеву формулу выполнимую тогда и только тогда, когда допускает Основная трудность доказательства — показать, что для каждой машины найдется алгоритм, который построит булеву формулу из за время, ограниченное полиномом. Этот полином зависит от

В силу леммы 10.1 каждый язык из распознается недетерминированной одноленточной машиной Тьюринга за полиномиальное время. Поэтому можно считать, что имеет всего одну ленту. Пусть состояниями будут а символами на ленте — Пусть временная сложность машины

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

Построим булеву формулу которая "моделирует" последовательность МО, проходимых машиной Любое присвоение значений истина (число 1) и ложь (число 0) переменным формулы соответствует самое большее одной последовательности МО, возможно незаконной (т. е. такой, которая не может на самом деле реализоваться). Булева формула примет значение 1 тогда и только тогда, когда это присваивание значений переменным соответствует последовательности ведущей к допуеканию входа. Иными словами, булева формула будет выполнима тогда и только тогда, когда допускает В качестве пропозициональных переменных в употребляются следующие переменные. Перечислим их вместе с их подразумеваемой интерпретацией.

1. тогда и только тогда, когда клетка на входной ленте машины содержит символ в момент времени Здесь .

2. тогда и только тогда, когда в момент времени находится в состоянии Здесь тогда и только тогда, когда головка в момент времени обозревает клетку. Здесь

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

Из этих пропозициональных переменных построим булеву формулу следуя структуре последовательности

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

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

Если допускает то найдется допускающая последовательность проходимая машиной в процессе обработки цепочки Для упрощения рассмотрений мы, не умаляя общности, будем считать, что машина модифицирована так, что она делает ровно шагов, а все ее МО содержат клеток. Этого можно добиться, заставив если нужно, работать после перехода в допускающее состояние, но не изменяя его и не сдвигая головку, и дополнив все МО нужным числом пустых символов. Поэтому будем строить как произведение семи формул которые утверждают, что допускающая последовательность МО, причем каждое имеет длину Утверждение о том, что допускающая последовательность МО, равносильно совокупности утверждений:

1) в каждом МО головка обозревает ровно одну клетку;

2) в каждом МО в каждой клетке ленты стоит ровно один символ;

3) каждое МО содержит в точности одно состояние;

4) при переходе от одного МО к следующему изменяется содержимое разве что клетки, обозреваемой головкой;

5) изменение состояния, положения головки и содержимого клетки при переходе от МО к следующему происходит в соответствии с функцией переходов машины

6) первое МО является начальным;

7) состояние в последнем МО - заключительное.

Построим булевы формулы соответствующие утверждениям 1—7.

1. А утверждает, что в каждый момент времени машина обозревает в точности одну клетку. Пусть утверждает, что в момент обозревается в точности одна клетка. Тогда где

Заметим, что если раскрыть выражение, обозначенное через то окажется, что формула А имеет длину и ее можно записать за такое же время.

2. В утверждает, что каждая клетка ленты в каждый момент времени содержит в точности один символ. Пусть утверждает, что клетка ленты в момент времени содержит ровно один символ. Тогда

где

Длина каждой формулы не зависит от , поскольку размер ленточного алфавита зависит только от машины Тьюринга Таким образом, В имеет длину

3. С утверждает, что в каждый момент времени машина находится в одном и только одном состоянии:

Так как число состояний машины постоянно, то С имеет длину .

4. D утверждает, что в любой момент времени можно изменить содержимое не более чем одной клетки

Формула утверждает, что либо

(а) в момент головка обозревает клетку либо

(б) -й символ записан в клетке в момент тогда и только тогда, когда он был записан там в момент

Поскольку утверждают, что в момент головка обозревает только одну клетку и клетка содержит лишь один символ, то в момент времени либо головка обозревает клетку либо содержимое клетки не меняется. Если раскрыть значение знака то длина будет

5. Е утверждает, что очередное МО машины получается из предыдущего одним переходом, разрешаемым функцией переходов машины Пусть означает одно из следующих утверждений:

(а) в момент клетка не содержит символа ,

(б) в момент головка не обозревает клетку i,

(в) в момент машина не находится в состоянии k,

(г) очередное машины получается из предыдущего переходом, разрешаемым функцией переходов машины

Тогда

где

Здесь пробегает по всем шагам машины возможным в случае, когда обозревает символ в состоянии Иными словами, для каждой тройки из существует одно значение I, для которого и число равно или зависимости от сдвигается ли головка влево

вправо или остается на месте Здесь 6 — функция переходов для Поскольку машина недетерминированна, то таких троек может быть несколько, но во всяком случае их число конечно. Таким образом, имеет ограниченную длину, не зависящую от Поэтому имеет длину утверждает, что выполнены начальные условия:

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

Булева формула это произведение Поскольку каждый из семи сомножителей состоит не более чем из символов, сама формула также состоит не более чем из символов. Так как мы считали каждую пропозициональную переменную за один символ, а в действительности переменные представляются цепочками длины то на самом деле границей на будет а это не превосходит где с — некоторая постоянная. Таким образом, длина цепочки полиномиально зависит от длины цепочки Должно быть ясно, что если даны цепочка и полином то формулу можно записать за время, пропорциональное ее длине.

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

Мы не наложили на язык допускаемый машиной никаких ограничений, кроме того, что он принадлежит классу Поэтому мы показали, что любой язык из полиномиально

трансформируем в задачу выполнимости булевых формул. Отсюда заключаем, что задача выполнимости NP-полна.

На самом деле мы доказали больше, чем утверждается в теореме 10.3. Говорят, что булева формула находится в конъюнктивной нормальной форме (КНФ), если она представляет собой произведение сумм литералов, где каждый литерал имеет вид х или для некоторой переменной х. Например, находится в нет. Формула построенная в доказательстве теоремы 10.3, практически находится в КНФ - ее можно представить в КНФ, увеличив длину не более чем в постоянное число раз.

Следствие. Задача выполнимости булевых формул, находящихся в КНФ, NP-полна.

Доказательство. Достаточно показать, что каждая из формул построенных в доказательстве теоремы 10.3, либо уже находится в КНФ, либо может быть преобразована в такую с помощью правил булевой алгебры, причем ее длина увеличится не более чем в постоянное число раз. Формула определенная равенством (10.1), уже находится в КНФ. Отсюда следует, что тоже находятся в КНФ. тривиально находятся в КНФ, поскольку произведения литералов.

D - формула вида Если раскрыть знак получится выражение

эквивалентное

Подставив (10.3) вместо всех вхождений (10.2) в получим формулу, эквивалентную исходной, но находящуюся в НКФ и превосходящую исходную формулу по длине не более чем в 2 раза.

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

Итак, формулу можно представить в КНФ, увеличив ее длину не более чем в постоянное число раз.

Мы только что показали, что задача выполнимости формул в КНФ NP-полна. Можно показать, что даже при более жестких ограничениях на вид формулы задача выполнимости булевых формул также NP-полна. Говорят, что формула находится в -конъюнктивной нормальной форме -КНФ), если она представляет собой произведение сумм, состоящих не более чем из литералов. Задача -выполнимости состоит в выяснении выполнимости формулы,

находящейся в -КНФ. Для и 2 известны детерминированные алгоритмы полиномиальной сложности, проверяющие -выполнимость. Ситуация (по-видимому) изменяется при как видно из следующей теоремы.

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

Доказательство. Покажем, что выполнимость формул в КНФ полиномиально трансформируема в -выполнимость. В данном произведении сумм заменим каждую сумму на

где новые переменные. Например, для выражение (10.4) принимает вид

Присвоить значения новым переменным так, чтобы подставляемая формула приняла значение 1, можно тогда и только тогда, когда один из литералов имеет значение 1, т. е. тогда и только тогда, когда исходная формула принимает значение 1. Допустим, что Тогда положим для для Подставляемая формула принимает значение 1. Обратно, допустим, что при некоторых значениях переменных подставляемая формула принимает значение 1. Если то одна из переменных должна иметь значение 1. Если то одна из переменных должна иметь значение 1. Если то для некоторого выполнены оба равенства откуда следует, что переменная должна иметь значение 1. В любом случае некоторая переменная должна иметь значение 1.

Длина формулы, получаемой в результате описанной выше замены, превосходит длину исходной формулы не более чем в постоянное число раз. Таким образом, по данной формуле в КНФ можно найти, применяя описанное выше преобразование к каждой сумме, формулу в -КНФ, выполнимую тогда и только тогда, когда выполнима исходная формула. Более того, легко показать, что можно найти за время, пропорциональное длине формулы выполняя преобразования очевидным образом.