( , ). Определение булевой формулы известно из математической логики. Формула выполнима, если найдется набор 0-1-значений переменных, на котором формула принимает значение 1.
Представим пропозициональные буквы в виде натуральных чисел, символ & как ·, символ Ú как +, символы: Ø , 1, 0, скобки - сохраним без изменения. Так что булева формула примет вид цепочки, составленной из символов натуральных чисел (которые мы представим в двоичной системе) и символов: ·, + , 0, 1, (, ).
Предложение.Язык ВЫП, состоящиий из цепочек, представляющих выполнимые булевы функции, принадлежит классу NP.
Доказательство. Недетерминированная машина Тьюринга, распознающая язык ВЫП, “угадывает” выполняющий набор T 0-1-значений пропозициональных переменных во входной цепочке w0, представляю щей булеву формулу, если такой набор существует. Угадывание есть параллельная работа на всех ветвях дерева вычислений недетерминированной машины. После подстановки значений 0-1 вместо пропозициональных переменных необходимо осуществить сдвиги, чтобы убрать
освободившиеся ячейки, занятые перед этим двоичными представлениями натуральных чисел, представляющих пропозициональные переменные. Если w0 (T) = 1, то машина допускает вход w0, даже если другие ветви не приводят в допускающее состояние, как следует из определения недетерминированной машины Тьюринга.
Значение формулы с помощью многоленточной недетерминированной машины Тьюринга можно осуществит за 0(n2) переходов. Таким образом, процесс распознавания ВЫП многоленточной машиной Тьюринга занимает время O(n2), поэтому язык ВЫПÎNP. “
Теорема Кука.Проблема ВЫП NP – полна.
Доказательство. Первая часть теоремы была доказана в предложении.
Покажем, что произвольный язык L из NP полиномиально сводится к языку ВЫП. Для языка L Î NP найдется недетерминированная одно- ленточная машина Тьюринга, обрабатывающая вход w длины n не более, чем за p(n) шагов вдоль любой ветви. По M, w будем строить булеву формулу w0, выполнимую тогда и только тогда, когда M допускает w. Сводящий алгоритм должен иметь полиномиальную сложность. Пусть M имеет состояния q1, q2 ,…,q s и ленточные символы X1, X 2,…,X m. Если M допускает вход w длины n, то делает это не более, чем за p(n) шагов. В этом случае найдется последовательность МО Q0, Q1,…,Q q, где Q0 – начальное, а Qq - заключительное (допускающее) МО, Qi -1 ├ Q i для 1£ i £q , q £ p(n), и ни одно МО не занимает на ленте более p(n) клеток.
Булева функция w0, которую мы собираемся построить, должна моделировать последовательность МО, проходимых машиной, и принимает значение 1, когда моделируемая последовательность МО приводит к допусканию входа. Другими словами, булева функция выполнима, когда M допускает вход w. В качестве пропозициональных переменных берем следующие предикаты:
1. С< i, j, t > = 1 тогда и только тогда, когда i-я клетка ленты машины M содержит символ X j в момент времени t, где 1£ i £ p(n), 1£ j £ m ,
0£ t £ p (n).
2. S< k, t > = 1 тогда и только тогда, когда M в момент времени t находится в состоянии q k, где 1£ k £ s , 0£ t £ p(n) .
3. H< i, t > = 1 тогда и только тогда, когда головка в момент времени t обозревает i-ю клетку, где 1£ i £ p(n) , 0£ t £ p(n).
Пропозициональных переменных всего O(p(n)2), их представление двоичными числами займет не более c log n разрядов, где c – константа, зависящая от p. Из этих пропозициональных переменных построим функцию w0, следуя структуре последовательности МО Q0, Q1,…,Q q.
Введем предикат U(x1,…,x r ), принимающий значение 1, когда в точности один из аргументов x1,…,xr принимает значение 1. Очевидно, что
U (x 1,…,x r) = (x 1 +…+ x r ) ( П (Øx i + Øx j )),
i ¹ j
где первый множитель означает, что по крайней мере одна из переменных xi истинна, остальные r (r-1)/2 сомножителя утверждают, что никакие две переменные не являются одновременно истинными. Длина цепочки, представляющей предикат U (x1,…,x r ), порядка O(r2).
Если машина M допускает вход w, то найдется последовательность МО Q0, Q1,…,Qq, проходимых машиной в ходе обработки цепочки w.
Поскольку сложность вычислений машины M на входе w длины n не превосходит p(n), для удобства будем считать, что машина делает точно p(n) шагов, допуская вход w, а все МО содержат p(n) клеток, в противном случае этого легко добиться, добавляя не меняющие последнее МО переходы, а также дополняя МО пустыми символами.
Построим семь формул, которые будут утверждать, что Q0, Q1,…,Q p (n) - допускающая последовательность, что фактически означает следующее:
1) в каждом МО головка обозревает одну клетку;
2) в каждом МО в каждой клетке записан один символ;
3) каждое МО содержит одно состояние;
4) при переходе Q i-1 ├ Q i (1£ i £ p(n)) изменяется разве что содержимое обозреваемой ячейки;
5) переход Q i-1 ├ Q i (1£ i £ p(n)) осуществляется в соответствии с функцией переходов машины M;
6) Q0 - начальное МО;
7) Q p( n) - заключительное МО.
Построим булевы формулы, интерпретируемые как утверждения 1-7:
1. A = A 0 A1…A p (n) утверждает, что в каждый момент времени маши
на M обозревает в точности одну клетку, соответственно At утверждает, что в момент времени t обозревается точно одна клетка, где
At = U (H< 1, t >, …,H< p(n), t >). Формула A имеет длину O(p3(n)).
3. B = П B it утверждает, что каждая клетка в каждый момент времени
i, t
содержит точно один символ, соответственно B it утверждает, что i-я клетка в момент времени t содержит точно один символ, где
B i t = U ( C < i, 1, t>, …, C < i, m, t >). Формула B имеет длину O(p2(n)).
3. С = П U (S < 1, t >,…, S <s, t >) утверждает, что в каждый момент
0£ t £ p( n)
времени машина M находится точно в одном состоянии. Формула С имеем длину O( p(n)).
4. D = П ( (С < i, j, t > º С < i, j, t + 1 >) + H < i, t > ) утверждает, что
i,j,t
в любой момент времени t можно изменить содержимое не более, чем одной ячейки, а формула (С < i, j, t > º С < i, j, t + 1 >) + H < i, t >
утверждает, что либо a) в момент времени t головка обозревает ячейку i,
либо b) в момент времени t+1 в клетке i записан символ j тогда и только тогда, когда он был записан там в момент времени t.
Длина формулы D равна O(p2(n)).
5. E = П Eijkt утверждает, что очередное МО получается из преды-
i , j, k, t
дущего одним переходом, согласно функции переходов d машины M, где Eij k t означает одно из следующих утверждений:
(a) в момент времени t клетка i не содержит символа j;
(b) в момент времени t головка не обозревает клетку i;
(c) в момент времени t машина M не нааходится в состоянии k;
(d) очередное МО машины M получается из предыдущего переходом, задаваемым функцией d.
E i j k t = Ø C < i, j, k > + Ø H< i, t > + Ø S< k, t > + å ( C<i, jl , t+1 >
S< kl , t+1> H< il , t+1>), i
где l пробегает по всем шагам машины M, когда M обозревает символ Xj в состоянии qk. Т.е. для каждой тройки < q, X, d > из d (q k, Xj) существует одно значение l, для которого Xjl = X, q kl = q и число il равно i -1, i или i+1 в зависимости от значения d, равного соответственно L, S, R. Поскольку машина M недетерминированная, таких троек
< q, X, d > может быть несколько, но их конечное число, таким образом
Eijkt имеет ограниченную длину, не зависящую от n. Формула E имеет длину O(p2(n)).
6. F = S< 1, 0 > H< 1,0 > П C< i, j i , 0 > П C< i, 1, 0 >,
1£ i £ n n£ i £ p(n)
где S< 1, 0 > утверждает, что в момент t =0 машина M находится в начальном состоянии q1; H< 1, 0 > утверждает, что M в момент t=0 обозревает самую левую ячейку ленты; П C< i, j i , 0 > утверждает, что
1£ i £ n
первые n клеток вначале содержат входную цепочку w; П C< i, 1, 0 >
n£ i £p( n)
утверждает, что остальные клетки вначале пусты (L соответствует в алфавите X1). Формула F имеет длину O(p(n)).
7. G = S < s, p(n) > утверждает, что M в конце концов приходит в заключительное состояние qs.
Булева формула w0 есть произведение ABCDEFG. Каждый сомножитель содержит не более, чем O(p3(n)) символов, так что сама формула w0 состоит не более, чем из O(p3(n)) символов. Представляя пропози циональные переменные цепочками длины O(log n), получим в качестве верхней границы длины w0 величину порядка O(p3(n) log n), что не превосходит cnp3(n), где c – некоторая константа. Таким образом, формулу w0 можно построить за время, пропорциональное ее длине.
По данной допускающей последовательности МО Q 0, Q 1,…,Q q можно, очевидно найти 0-1-набор для пропозициональных переменных C< i, j, t>, S< k, t >, H< i, t >, на котором w0 истинно. Обратно, по 0-1-набору, обращающем w0 можно найти допускающую последовательность МО. Таким образом, формула w0 выполнима тогда и только тогда, когда M допускает цепочку w. Тем самым построен алгоритм полиномиальной сложности, сводящий язык L Î NP к языку ВЫП. Тем самым задача ВЫП NP-полна. “
Следствие.Задача выполнимости булевых формул, находящихся в конъюнктивной нормальной форме (ВКНФ), NP – полна. “
Говорят, что формула находится в k-конъюнктивной нормальной форме (k-КНФ), если она есть произведение сумм, состоящих не более чем из k литералов. Для k=1, 2 известны детерминированные полиномиальной сложности алгоритмы, распознающие языки 1-КНФ и 2-КНФ.
Рассматриваемая ниже задача 3-выполнимости, как и задачи ВЫП и ВКНФ, представляют интерес не только сами по себе, но и в связи с тем, что они полиномиально сводятся еще к ряду задач, откуда следует NP- полнота последних.
Теорема.Задача 3-выполнимости NP-полна.
Доказательство. Покажем, что выполнимость формул в КНФ полиномиально сводится к 3-выполнимости. Заменим каждый член (x1 + x2+…+x k),
на (x 1 + x 2 + y 1)(x 3 + y 1 + y 2)( x 4 + y 2 + y 3)…(x k -1 + x k+ yk -3)
(k ³ 4), где y 1, y 2,…,y k-3 - новые переменные.
Присвоить значения новым переменным так, чтобы вновь полученная формула приняла значение 1, можно тогда и только тогда, когда исходная формула принимает значение 1.
Длина формулы, получаемой в результате описанной замены, превосходит длину исходной формулы не более, чем в постоянное число раз. Таким образом, по данной формуле E в КНФ можно найти формулу E’в 3-КНФ, выполнимую тогда и только тогда, когда выполнима исходная формула. Причем, E’ находится за время, пропорциональное длине формулы E. “
Другие NP – полные задачи1)
Введем определения. Пусть G = (V, E ) граф.
k - кликой в неориентированном графе G называют k – узельный полный подграф графа G.
k - узельным покрытием неориентированного графа G называется k – подмножество S множества V, что каждое ребро графа G инцидентно некоторому узлу из S.
Подмножество I узлов неориентированного графа G называется независимым множеством, если никакие два узла из I не соединены между собой ребром из G.
Гамильтоновым циклом называется цикл в неориентированном графе G, содержащим все узлы из V.
Неориентированный граф G называется k – раскрашиваемым, если существует такое приписывание целых чисел 1,2,…,k, называемых цветами, узлам графа, что никаким двум смежным узлам не приписан один и тот же цвет.
Множеством узлов, разрезающих циклы, называется такое подмножество S Í V, что каждый цикл в ориентированном графе G содержит узел из S.
Примерами задач, принадлежащих классу NP, являются следующие:
1. О клике. Содержит ли данный неориентированный граф k – клику ?
2. Об узельном покрытие. Имеет ли данный неориентированный граф
k - узельное покрытие ?
3. О гамильтоновом цикле. Имеет ли данный неориентированный граф гамильтонов цикл ?
4. О раскрашиваемости. Является ли данный неориентированный граф k – раскрашиваемым ?
5. О множестве узлов, разрезающих циклы. Имеет ли данный ориентированный граф k – элементное множество узлов, разрезающих циклы ?
6. Об ориентированном гамильтоновом цикле. Имеет ли даный ориентированный граф ориентированный гамильтонов цикл ?
7. О покрытие множествами. Существует ли для данного семейства множеств S1,…,Sn такое подсемейство из k множеств S i 1 ,…, S i k , что
È S i j = È Sj ?
j =1…k j =1…n
На рис. 10.6 10.12 указана последовательность полиномиальных сводимостей перечисленных проблем.
