Главная Промышленная автоматика.

ства множеств S, Sg,. . ., S„) такое подсемейство из k множеств S,.j, S,,. . ., Si, что

и S,,= и Sj?

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

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

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

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

Доказательство. Мы уже знаем, что задача выполнимости принадлежит (КЗ*. Остось показать, что всякий язык L из о)Т5* полиномиально трансформируем в задачу выполнимости. Пусть М - недетерминированная машина Тьюринга, распознающая L за полиномиальное время, и пусть на ее вход подана цепочка Из М и а; можно построить булеву формулу Wo, выполнимую тогда и только тогда, когда М допускает w. Основная трудность доказательства - показать, что для каждой машины М найдется алгоритм, который построит булеву формулу Wo из w за время, ограниченное полиномом. Этот полином зависит от М.

В силу леммы 10.1 каждый язык изо)Т5* распознается недетерминированной одноленточной машиной Тьюринга за полиномиальное время. Поэтому можно считать, что М имеет всего одну ленту. Пусть состояниями М будут 9i, а,- . ., 7s, а символами на ленте- Xi, Хг,. . ., Х„. Пусть р{п) - временная сложность машины М.

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

бы однр такая последовательность МО Qo, Qi.....Q,, что Qo -

начальное МО, Qj-i \- Qi для l<t<9, - допускающее МО, 9<р (п) и ни одно МО не занимает более р (п) клеток на ленте.

1) Конечные множества мы кодируем цепочками вида {("i, (j, .... где »у- десятичные (или двоичные) целые числа, представляющие элементы этих множеств. Если во всех множествах всего п разных элементов, мы представляем /-Й элемент целым числом /.



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

1. С<1, /, />=1 тогда и только тогда, когда i-я клетка на входной ленте машины М содержит символ Xjb момент времени Здесь Kj<p(n), 1</<т и 0<i<p(n).

2. S<k, f>=l тогда и только тогда, когда М в момент времени t находится в состоянии q. Здесь l</<s и 0<<р (п).

3. Я<1, />=1 тогда и только тогда, когда головка в момент времени t обозревает t-ю клетку. Здесь ltp(n) и 0 <р(п).

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

Из этих пропозициональных переменных построим булеву формулу Wo, следуя структуре последовательности МО Qo, Qi.....Q,.

В этом построении мы воспользуемся предикатом U {Xi, х.....,Хг),

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

U(Xi,x......x,) = {Xi-\-Xi-\-...-\-x,)fY[ {-Xl + -xЛ. (10.1)

Первый множитель в (10.1) утверждает, что по крайней мере одна из переменных Xt истинна. Остальные г (г-1)/2 множителей утверждают, что никакие две переменные не являются истинными одновременно. Заметим, что формальная запись формулы U {хи Хз,. • ., Хг) имеет длину 0(r)).

) Напомним, что мы считаем переменную одним символом. Строго говоря, потребуется 0(r4ogr) и, значит, не более 0(о символов.



Если М допускает w, то найдется допускающая последовательность МО Qo, Qi,. • •. Qq, проходимая машиной М в процессе обработки цепочки W. Для упрощения рассмотрений мы, не умаляя общности, будем считать, что машина М модифицирована так, что она делает ровно р (п) шагов, а все ее МО содержат р (п) клеток. Этого можно добиться, заставив М, если нужно, работать после перехода в допускающее состояние, но не изменяя его и не сдвигая головку, и дополнив все МО нужным числом пустых символов. Поэтому будем строить Wo как произведение семи формул А, В,. . ., G, которые утверждают, что Qo, Qi,. . ., Q, - допускающая последовательность МО, причем каждое МО Qi имеет длину р{п) и q=p{n). Утверждение о том, что Qo, Qi,. . ., Qpn) - допускающая последовательность МО, равносильно совокупности утверждений:

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

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

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

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

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

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

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

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

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

Л, = {/(Я<1, Я<2. />.....Я<р(п),

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

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

B,t = U{C<i, 1, t>, C<i, 2,t>.....C<i, m, ty).

Длина каждой формулы Вц не зависит от п, поскольку размер m ленточного алфавита зависит только от машины Тьюринга М. Таким образом, В имеет длину 0{р»(п)).





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 [137] 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0019