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

Задача о клике принадлежит классу оЛГ5*. Недетерминированная машина Тьюринга сначала может "догадаться", какие k узлов составляют полный подграф, а затем проверить, что любая пара этих узлов соединена ребром, при этом для проверки достаточно О (л) шагов, где п - длина кода задачи о клике. Это демонстрирует "силу" недетерминизма, ибо все подмножества из k узлов проверяются "параллельно" независимыми экземплярами распознающего устройства. Граф на рис. 10.5 содержит три 3-клики, а именно

{fl, fa, 4}, {f2, V», U4} и {Уа, Vl, V).

Мы увидим позже, что задача о клике NP-полна. В настоящее время не известны способы решения задачи о клике за детерминированное полиномиальное время.

Пример 10.4. Булеву формулу (Р1+р2)«Рз можно представить, цепочкой (1-1-2)3, где число i представляет переменную р. Рассмотрим язык L, образованный всеми цепочками, представляющими выполнимые булевы формулы (т. е. формулы, принимающие значение 1 на некотором наборе 0-1-значений переменных). Мы утверждаем, что L принадлежит оЛГ5*. Недетерминированный алгоритм, распознающий L, начинает с того, что "угадывает" выполняющий набор 0-1-значений пропозициональных переменных во входной цепочке, если такой набор существует. Затем угаданное значение (О или 1) каждой переменной подставляется вместо всех вхождений этой переменной во входную цепочку. Чтобы закрыть дыры, образующиеся в цепочке в результате подстановки одного символа О или 1 вместо десятичного представления пропозициональной переменной, потребуются некоторые сдвиги цепочки. Далее вычисляется значение полученного выражения, чтобы проверить его совпадение с 1.

Это вычисление осуществляется за время, пропорциональное длине выражения, многими алгоритмами синтаксического анализа (см. Ахо, Ульман [1972]). Но даже и без них не трудно вычислить значение булевой формулы за О(п) шагов. Следовательно, некоторая недетерминированная машина Тьюринга допускает выполнимые булевы формулы с полиномиальной временной сложностью, и потому задача распознавания выполнимости булевых формул принадлежит ЖЗ. Снова отметим, что недетерминизм пригодился, чтобы "параллелизовать" задачу, поскольку "угадывание" правильного решения в действительности означает параллельную проверку всех возможных решений. Как будет показано позже, эта задача также NP-полна. □

Часто нас интересуют задачи оптимизации, например нахождение наибольшей клики в графе. Многие такие задачи можно преобразовать за полиномиальное время в задачи распознавания языка. Например, наибольшую клику в графе G можно найти так:

14» 419



Пусть п - длина представления графа G. Для каждого /г от 1 до п выясняем, содержит ли граф клику размера к. Установив таким образом размер т наибольшей клики, удаляем по одному узлу до тех пор, пока удаление очередного узла v не разрушит все оставшиеся клики размера т. Затем рассмотрим подграф G, состоящий из всех узлов графа G, смежных с v. Рекурсивно вызывая этот процесс, находим клику С размера т-1 в G. Наибольшей кликой для G будет CUv.

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

С помощью двоичного поиска (разд. 4.3) часто можно решить задачу оптимизации вида "найти такое наибольшее к, что Р{к) истинно", гдеР- некоторое условие, а число допустимых к оценивается экспонентой от длины п. описания задачи. Если из истинности Р(к) следует истинность Р (i) для Кк, а к изменяется от О до с", где с - некоторая постоянная, то наибольшее к, для которого истинно Р{к), можно найти двоичным поиском, проведя log с"=п log с проверок условия Р{к). Читателю снова предлагаем убедиться в том, что оптимальное значение к можно найти за время, полиномиально зависящее от п и от наибольшего времени проверки Р{к).

Разработку техники подобного рода предоставляем изобретательности читателя и в дальнейшем будем заниматься только задачами, требующими ответа "да" или "нет".

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

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

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



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

Определения. Пусть G=(V, Е) - неориентированный граф.

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

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

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

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

Определения. Пусть G={V, Е) - ориентированный граф.

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

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

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

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

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

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

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

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

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

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

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

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

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





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.006