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

доказать, что некоторые языки не менее "трудны", чем любой язык из o)V5, в том смысле, что если бы у нас был детерминированный алгоритм, распознающий один из этих "не менее трудных" языков за полиномиальное время, то можно было бы для каждого языка из oJ\"5* найти детерминированный алгоритм, распознающий его за полиномиальное время. Такие языки называются NP-полными.

Определение. Язык Lq из ЖЗ называется полным для недетерминированного полиномиального времени (или NP-полным), если выполнено следующее условие: по данному детерминированному алгоритму распознавания Lo с временной сложностью Т{п)п и любому языку L из можно эффективно найти детерминированный алгоритм, распознающий L за время Т (р (л)), где р - некоторый полином, зависящий от L. Говорят, что L сводится к Lq.

NP-полноту языка Lq можно доказать, показав, что Lo принадлежит off5 и каждый язык L оЛГ можно "полиномиально трансформировать" в Lo.

Определение. Язык L называется полиномиально трансформируемым в Lo, если некоторая детерминированная машина Тьюринга М с полиномиально ограниченным временем работы преобразует каждую цепочку W в алфавите языка L в такую цепочку Wo в алфавите языка Lo, что wL тогда и только тогда, когда WoQ,Lo.

Если язык L трансформируем в Lo и Lo распознается некоторым детерминированным алгоритмом А с временной сложностью Т (п)п, то можно выяснить принадлежность цепочки w языку L, преобразовав W в Wo с помощью машины М и затем применив А для выяснения принадлежности Wo языку Lo. Если время работы машины М ограничено полиномом р(п), то а;ор (а;). Таким образом, существует алгоритм, выясняющий принадлежность w языку L за время p(\w\)+T{p(\w\))2T{p(\w\)). Если бы функция Т была полиномом (т. е. язык Lo принадлежал бы 5), то этот алгоритм, распознающий L, работал бы полиномиально ограниченное время, и язык L также принадлежал бы Э.

Некоторые авторы, действительно, определяют язык Lo как NP-полный, если он принадлежит и каждый язык из o!fS полиномиально трансформируем в Lo. Это определение представляется более узким, чем предыдущее, хотя не известно, приводят ли указанные два определения NP-полных языков к разным классам. Определение, основанное на сводимости, означает, что если Мо - детерминированная машина Тьюринга, распознающая NP-полный язык Lo за время Т{п), то всякий язык из о)* можно распознать за время Т{р(п)), где р - некоторый полином, с помощью детерминированной машины Тьюринга, которая обращается к Л1о как к подпрограмме нуль или более раз. Определение, основанное на трансфор-



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

Какое бы из этих определений ни взять, ясно, что если некоторый детерминированный алгоритм распознает Lo за полиномиальное время, то все языки из сЛГ* можно распознать за полиномиальное время. Таким образом, либо все NP-полные языки принадлежат , либо ни один из них не принадлежит 5*. Первое верно тогда и только тогда, когда Э=ЖЗ. К сожалению, в настоящее время мы можем лишь выдвинуть гипотезу о том, что 5* - собственный подкласс класса ЖЭ.

10.3. ЯЗЫКИ и ЗАДАЧИ

Мы определили 5* и ЖЗ как классы языков. Причина этого двоякая. Во-первых, это упрощает систему обозначений. Во-вторых, задачи из разных областей, таких, как теория графов и теория чисел, часто можно сформулировать как задачи распознавания языков. Например, рассмотрим задачу, которая при каждом значении входных данных требует ответа "да" или "нет". Можно закодировать все возможные значения входных данных такой задачи в виде цепочек и переформулировать ее как задачу о распознавании языка, состоящего из всех цепочек, представляющих входные данные нашей задачи, которые приводят к ответу "да". Такие способы кодирования уже встречались нам в гл. 9, где задачи идентификации формулировались в терминах задач распознавания языков. Однако надо аккуратно выбирать эти кодирования, потому что от них может зависеть временная сложность задачи.

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

1. Целые числа будем представлять в десятичной системе счисления.

2. Узлы графа будем представлять целыми числами 1, 2,..., п, закодированными как десятичные числа в соответствии с соглашением 1. Ребро будем представлять цепочкой (t,, ij), где ti и 12.- десятичные представления пары узлов, определяющей это ребро.

3. Булевы выражения (формулы) с п пропозициональными переменными будем представлять цепочками, в которых » представляет "и", + представляет "или", г- представляет "не"1), а целые числа 1, 2,.. ., п представляют пропозицио-

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



нальные переменные. Знак *, когда можно, опускается. Если нужно, будем ставить скобки.

Теперь мы можем сказать, что задача принадлежит 5* или ЖЗ, если ее стандартный код принадлежит 5 или jfS соответственно.

Пример 10.3. Рассмотрим задачу о клике для неориентированных графов, k-кликой в графе G называют/г-узельный полный подграф (каждая пара различных узлов в этом подграфе соединена ребром) графа G. Задача о клике формулируется так: содержит ли данный граф G /г-клику, где k - данное целое число?

Пример задачи о клике для графа G на рис. 10.5 при =3 можно закодировать цепочкой

3 (1,2) (1,4) (2,3) (2,4) (3,4) (3,5) (4,5).

Первое число представляет значение k. За ним идут пары узлов, соединенных ребрами, причем узел Vi представлен числом i. Таким образом, ребра в порядке перечисления выглядят так: {vi, v,),

(Vi, Vi).....(Vt, Us).

Язык L, представляющий задачу о клике, образуют такие цепочки вида

k Пик) (h,h)--(im.U).

что граф с ребрами (tV, /V), l<r</7i, содержит /г-клику. Задачу о клике могут представлять и другие языки. Например, можно было бы потребовать, чтобы постоянная k стояла за, а не перед графом. Или можно было бы использовать двоичные числа вместо десятичных. Но для любых двух таких языков должен существовать такой полином р, что цепочку w, представляющую частный случай задачи о клике в одном языке, можно за время p(\w\) преобразовать в цепочку, представляющую тот же частный случай этой задачи в другом языке. Таким образом, когда речь идет о принадлежности классу или оЛГ, точный выбор языка для представления задачи о клике неважен, если применяется "стандартное" кодирование. □


Рис. 10.5. Неориентированный граф.





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