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

Тогда существует такое ребро e={v, w), что с,=с„=с. А тогда каждое из множеств S„c и Sok содержит [е, с], и потому не является точным покрытием вопреки предположению. □

10.6. ЗАДАЧИ С ПОЛИНОМИАЛЬНО ОГРАНИЧЕННОЙ ПАМЯТЬЮ

Класс ЛЗ* содержится в другом естественном классе трудных задач. Этот класс, обозначаемый 5*-SPACE, образован языками, допускаемыми детерминированными машинами Тьюринга с полиномиально ограниченной памятью (т. е. емкостной сложностью).

Вспомним, что по теореме 10.1, если L допускается некоторой НМТ с емкостной сложностью р (п), где р - полином, то он допускается некоторой ДМТ с емкостной сложностью р(п). Поэтому 5*-SPACE включает в себя также все языки, допускаемые НМТ с полиномиально ограниченной памятью. Так как каждая НМТ с полиномиально ограниченным временем имеет полиномиально ограниченную память, ясно, что oif5*-TIMEs5>-SPACE (рис. 10.13). Кроме того, поскольку 5»-Т1МЕоЛГ5»-Т1МЕ5>-8РАСЕ, то из равенства 5-TlME=5-SPACE следует, что 5>-Т1МЕ=оЛГ5»-Т1МЕ, а потому распознавание детерминированным алгоритмом с полиномиально ограниченным временем работы любого языка из 5*-SPACE еще менее вероятно, чем распознавание таким алгоритмом любого языка из o)V*-TIME.

Можно указать довольно естественный язык полный для -SPACE. Так называется язык, который принадлежит 5*-SPACE и удовлетворяет следующему условию: если он допускается какой-то детерминированной МТ с ограниченным функцией Т{п) временем работы, то для каждого языка L ё 5*-SPACE найдется детерминированная МТ с временем работы, ограниченным функцией т(р (п)), где Pi - полином, зависящий от L. (Здесь слово "детерминированная" можно заменить на "недетерминированная".) Поэтому если Е.еЗ-ТШЕ, то 5-TIME=o5»-TIME=5-SPACE. Если L, 6 оЛГ5-Т1МЕ, то оЛГ5»-Т1МЕ=5>-5РАСЕ. Язык - это множество регулярных выражений, дополнения которых представляют непустые множества.


(-ПМЕ

Рис. 10.13. Взаимосвязь памяти и времени.




Лемма 10.2. Пусть M={Q, Т, I, б, Ь, о, qt) - одноленточная ДМТ с памятью, ограниченной полиномом р. Тогда найдется такой полином р, что если х1* и \х\=п, то за время р (п) можно построить регулярное выражение R, дополнение которого представляет пустое множество тогда и только тогда, когда М не допускает х.

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

Регулярное выражение R можно представлять себе как способ описания последовательностей МО машины М, которые не допускают цепочку X. Для наших целей понадобится алфавит Л=Ги и {[qX]\qа X Т}. Символ IqX] из QXГ представляет клетку входной ленты машины М, обозреваемую головкой, причем клетка содержите, а М находится в состоянии9. Если М допускает х, то в соответствующей последовательности шагов на каждом шаге используется не более р(\х\) клеток налейте. Поэтому можно представлять МО цепочкой Wi, состоящей ровно из р(л) символов, причем все они, кроме одного, взяты из Т; этот один символ имеет вид [qX]. Последовательность шагов машины М можно представить цепочкой #Wi#W2#. . .Wi# для некоторого kl, где # - новый разделительный символ и каждая цепочка Wi из А* представляет некоторое МО, \Wi\=p{n). При необходимости в это МО добавляются пустые символы (чтобы сделать длину цепочки Wt равной р(п)).

Л\ы хотим построить регулярное выражение R так, чтобы оно представляло те цепочки из (А и {#})*. которые не описывают допускающие вычисления машины М для входа х. Поэтому R будет представлять все цепочки из (А и {#})* тогда и только тогда, когда М не допускает х. Цепочка «/ € (А U {#})* не будет представлять допускающее вычисление машины М только тогда, когда выполнено одно или более из следующих четырех условий. Мы считаем, что \х\=п.

1. Цепочка у ни для какого kl не имеет вида #Wi#W2#. . . .. где \Wi\=p(n) для каждого /, life, и все символы цепочки Wi принадлежат Т, за исключением одного, который имеет вид [qX].

2. Начальное МО Wi неправильно, т. е. цепочка у не начинается с #[qoai]aa. . .a„bb. . . b#, где x=ai. . .а„, а число пустых символов равно р(п)-п.

3. М никогда не попадает в заключительное состояние, т. е. никакой символ вида IfX] не входит в у.



i. В У есть такие два соседних МО, что второе не получается из первого за один шаг работы машины М.

будет иметь вид A+B+C+D, где А, В, С, D - регулярные выражения, представляющие множества, определяемые условиями 1-4 соответственно.

Полезно ввести сокращения для записи регулярных выражений. Если мы пользуемся алфавитом S={ci, Cj,. ... с„}, то S будет обозначать регулярное выражение С1+С2+. . .+с„, а S - регулярное выражение (S)(S). . .(S) (i раз), т. е. цепочки длины i в алфавите S. Заметим, что длина регулярного выражения, обозначенного через S, равна 2т-1, а через S равна j(2m+l). Аналогично, если St-Si={di, di,. . ., d), то Si-Sj будет обозначать регулярное выражение di4-daH-. • .+dr-

При таких соглашениях регулярное выражение А можно записать в виде

Л = А + А»#Л» + А(А +#)» + (А + #)»Д + (А + #)*#Г*#(Д+#)* + (А + #)• # А» (Q X Т) А* (Q X Г) А» # (А +#)• + (А + #)• # ДР А» # (А + #)•

+ Л„ + 4 + ...+Лр(„, 1, (10.7)

где At будут определены позже. Первые семь слагаемых в (10.7) представляют соответственно цепочки

1) без #,

2) лишь с одним символом #,

3) не начинающиеся с #,

4) не кончающиеся на #,

5) не содержащие символа из QxT между двумя #,

6) содержащие более одного символа из QxT между двумя #,

7) содержащие более р (л) символов из А между символами #.

Остальные слагаемые/4 j определяются равенствами Ai={A+#)* #Д#(А+#)* и в совокупности представляют множество цепочек, содержащих менее р (л) символов из А между двумя символами #.

Предлагаем читателю проверить, что регулярное выражение (10.7) на самом деле представляет цепочки, удовлетворяющие условию 1. Кроме того, первые шесть слагаемых имеют фиксированную длину, зависящую только от М. Длина седьмого, очевидно, есть 0(р{п)). Слагаемое At имеет длину 0{i), так что сумма длин всех А, и, значит, длина выражения (10.7) есть 0{р(п)), причем мультипликативная постоянная зависит только от Л1, но не от х. Далее, легко проверить, что выражение (10.7) легко выписать за время, полиномиально зависящее от п.

Теперь заметим, что для В, С и D достаточно написать выражения, представляющие все цепочки, которые удовлетворяют условию





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