1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 89
Текст из файла (страница 89)
Тогда для каждого о найдется такое единственное число с„что З„Е К Это вытекает из того, что каждый узел о должен принадлежать точно одному множеству из Рт", Мы утверждаем, что для получения к-раскраски графа 6 можно раскрасить каждый узел о в цвет с,. Допустим, что это ие так. ГЛ. 1О. ИР-ПОЛНЫЕ ЗАДАЧИ Тогда существует такое ребро е=(а, тс), что с,=с =с. А тогда каждое из множеств 5 и 5 содержит [е, с), и потому ех не является точным пакрйтием вопреки предположению.
Д 10.6. ЗАДАЧИ С ПОЛИНОМИАЛЬНО ОГРАНИЧЕННОЯ ПАМЯТЬЮ Класс е1ГУ содержится в другом естественном классе трудных задач. Этот класс, обозначаемый У-БРАСЕ, образован языками, допускаемыми детерминированными машинами Тьюринга с полиномиально ограниченной памятью (т. е. емкостной сложностью). Вспомним, что по теореме 10.1, если Е допускается некоторой НМТ с емкостной сложностью р(п), где р — полинам, то он допускается некоторой ДМТ с емкостной сложностью р'(и). Поэтому У-БРАСЕ включает в себя также все языки, допускаемые НМТ с палиномиально ограниченной памятью. Так как каждая НМТ с полиномиально ограниченным временем имеет полиномиально ограниченную память, ясно, что М'У-Т1МЕе:-У-БРАСЕ (рис.
10.!3). Кроме того, поскольку У-Т1МЕ~4ГУ-Т1МЕыУ-БРАСЕ, то из равенства У-Т1МЕ=У-БРАСЕ следует, что У-Т1МЕ=Д'У-Т!МЕ, а потому распознавание детерминированным алгоритмом с полиномиально ограниченным временем работы любого языка из У-БРАСЕ еще менее вероятно, чем распознавание таким алгоритл1ам любого языка ИЗ,М'У-Т1МЕ. Можно указать довольно естественный язык Е„полный для У-БРАСЕ. Так называется язык, который принадлежит У-БРАСЕ и удовлетворяет следующему условию: если он допускается какой-то детерминированной МТ с ограниченным функцией Т(п) временем работы, то для каждого языка Е бУ-БРАСЕ найдется детерминированная МТ с временем работы, ограниченным функцией Т(р, (и)), где р — полинам, зависящий от Е. (Здесь слово "детермийированная" можно заменить на "недетерминированная".) Поэтому если Е, Е У-Т1МЕ, та У-Т1МЕ=е)1"У-Т1МЕ=У-БРАСЕ.
Если Е,ЕФУ-Т1МЕ, то ФУ-Т1МЕ=У-БРАСЕ. Язык Е,— это множество регулярных выражений, дополнения которых представляют непустые множества. Рис. ГВЛЗ. Взаимосвязь памяти и времени. 44В ~ь.в. злдлчи с полиномихльно огглничвннои плмятью Лемма 10.2. Пусть М=Я, Т, 1, б, Ь, о„о~) — одноленточная ДМТ с памятью, ограниченной полиномом р. Тогда найдется такой полинам р', что если хЕ г' и [х[=п, то за время р'(и) можно построить регулярное выражение П„, дополнение которого представляет пустое множество тогда и только тогда, когда М не допускает х.
Д о к а з а т е л ь с т в о. Доказательство очень похоже на доказательство теоремы 10.3. Там для описания вычислений машины Тьюринга использовались булевы функции. Здесь у нас будет язык регулярных выражений. Регулярные выражения можно записывать в компактной форме, и с их помощью удается выразить факты о последовательностях МО, существенно более длинных, чем сами регулярные выражения. Регулярное выражение )т„можно представлять себе как способ описания последовательностей МО машины М, которые не допускают цепочку х. Для наших целей понадобится алфавит й=Тц [) ([оХ)[оЕЯ и ХЕТ). Символ [оХ) из ЯкТ представляет клетку входной ленты машины М, обозреваемую головкой, причем клетка содержит Х, а М находится в состояниями.
Если М допускает х, то в соответствующей последовательности шагов на каждом шаге используется не более р([х[) клеток на ленте. Поэтому можно представлять МО цепочкой вь состоящей ровно из р(п) символов, причем все они, кроме одного, взяты из Т; этот один символ имеет вид [дХ). Последовательность шагов машины М можно представить цепочкой фш,ЯюД~...гм„ф для некоторого й)1, где ~ — новый разделительный символ и каждая цепочка ич из Гт» представляет некоторое МО, [в, [=р (и). При необходимости в это МО добавляются пустые символы (чтобы сделать длину цепочки ич равной р(п)).
Мы хотим построить регулярное выражение Я„так, чтобы оно представляло те цепочки из (Л0(ф))', которые не описывают допускающие вычисления машины М для входа х. Поэтому Я„будет представлять все цепочки из (а 0 (ф.))* тогда н только тогда, когда М не допускает х. Цепочка у Е (й О (4е))ь не будет представлять допускающее вычисление машины М только тогда, когда выполнено одно или более из следующих четырех условий. Мы считаем, что [х[=п. 1.
Цепочка у ии для какого й)~1 не имеет вида фв,г[гто г[Е... ...шеф, где [иЧ[=р(п) для каждого 1, 1» 1(й, и все символы цепочки ин принадлежат Т, за исключением одного, который имеет вид [уХ). 2. НачальноеМО ш, неправильно, т. е. цепочка у не начинается с 4.'[д,а,[а,...а„ЬЬ...ЬФ, где х=а,...а„, а число пустых символов равно р(п) — и.
3. М никогда не попадает в заключительное состояние, т. е. никакой символ вида !о,Х) не входит в у. ГЛ. 1О. НР-ПОЛНЫЕ ЗАДАЧИ 4. В у есть такие два соседних МО, что второе не получается из первого за один шаг работы машины М. Я, будет иметь вид А+В+С+О, где А, В, С, А) — регулярные выражения, представляющие множества, определяемые условиями 1 — 4 соответственно. Полезно ввести сокращения для записи регулярных выраже- ний. Если мы пользуемся алфавитом 5=(с„с„..., с„), то 5 будет обозначать регулярное выражение с,+с,+...+с„, а 5'— регулярное выражение (5)(5)...(5) (1 раз), т.
е. цепочки длины 1 в алфавите 5. Заметим, что длина регулярного выражения, обозна- ченного через 5, равна 2гл — 1, а через 5' равна 1(2ПО+1). Анало- гично, если 5,— 5О=-(О(ь О(„..., О(„), то 51 — 5, будет обозначать регулярное выражение О(,+О(,+...+и'„. При таких соглашениях регулярное выражение А можно запи- сать в виде А = А*+ Ь'.ФЬ'+ Ь (б +Ф)'+(б + Ф)' Л +(б 1 ф)*ОТ'~(Л+Ф)* +(7+я Рб Дхт)Ь Дхт)и Д(7А+Р) 1 (А 1 ~)э (ебРРО+1А, ° ч.(А, 1 ~)е +А,+А,+ ° ° +Ар(р)-А (10.7) где АО будут определены позже. Первые семь слагаемых в (10.7) представляют соответственно цепочки 1) без 4Е, 2) лишь с одним символом Ф., 3) не начинающиеся с 46, 4) не кончающиеся на .ф, б) не содержащие символа из (~ХТ между двумя ~, 6) содержащие более одного символа из СгХТ между двумя 4е, 7) содержащие более р(л) символов из б между символами 4е.
Остальные слагаемые А, определяются равенствами А Π— — (А+4~)* 4ЕЛ'Ф(б+~)* н в совокупности представляют множество цепочек, содержащих менее р (и) символов из б между двумя символами 4Е. Предлагаем читателю проверить„что регулярное выражение (10.7) на самом деле представляет цепочки, удовлетворяющие ус- ловию 1. Кроме того, первые шесть слагаемых имеют фиксированную длину„зависящую только от М.
Длина седьмого, очевидно, есть 0(р(л)). Слагаемое А~ имеет длину 0(1), так что сумма длин всех А, и, значит, длина выражения (10.7) есть 0(р'(л)), причем мультипли- кативная постоянная зависит только от М, но не от х. Далее, легко проверить, что выражение (10.7) легко выписать за время, поли- номиально зависящее от и. Теперь заметим, что для В, С и 1) достаточно написать выраже- ния, представляющие все цепочки, которые удовлетворяют условию 10.6. ЗАДАЧИ С ПОЛИНОМИАЛЬНО ОГРАНИЧЕННОЙ ПАМЯТЬЮ 2 , 3 или 4, но нарушают условие 1, т. е.
цепочки вида 4те,46... ...ш446, где ~п4<=р (и) и ПЧ ~ Т" (Я~С Т)Т'. Однако для простоты мы выпишем выражения, определяющие множества цепочек, которые удовлетворяют условию 2, 3 или 4 и нарушают условие 1, а также некоторых цепочек, удовлетворяющих не только условию 2, 3 или 4, но и условию 1. Так как цепочки последнего типа уже представлены в В, в силу определения выражения й, их наличие или отсутствие в В, С и Р несущественно. Считая, что входная цепочка имеет вид я=а,а,...а„, полагаем В Вз+Вз ( +Врми гДе В, =4~ (Д.— '14„а,<) ДР<">-'4~ (Д+4~)', ~ьу-~(Т (и,)) ди >-с~ (д ( (А) 1<(~л 4 фдк-1(Т (1з)) дров 8 -се(д 1 ф)г и (ч'р(л) Таким образом, В~ отличается от начального р40 по крайней мере в 1-м входном символе.
Очевидно, В имеет длину 0(р'(и)), причем мультипликативная постоянная зависит только от М. Положим С=((Д+ф) — ((дг)ИТ))Р. Длина этого выражения, конечно, зависит только от М. Наконец, построим Р. Пусть дана цепочка у, представляющая правильное (т.
е. позволяющее фактически реализовать) вычисление машины М. Тогда у имеет вид 4ИЕ,4йп,7~...ш44Ь, где ~в; ~=р(а) для каждого 1 и иь+г — это МО, которое получается из иь за один шаг работы машины М. Заметим, что поданным трем последовательным символам с,с,с, цепочки у можно однозначно определить символ, назовем егог(с,с,с,), который должен появиться в цепочке на р (л)+1 символов правее с,.
Например, если с„с, и с, все принадлежат Т, то с, не может измениться в следующем МО, так что 1(с,с,с,)= =с,. Если с, и с, принадлежат Т, сз=(дХ) — символ из ОхТ и 6(д, Х)=(р, Х, Ь), то Г(с,сзс,)=(раз). Остальные правила для определения 1, включая те, что соответствуют случаю, когда с, или с, принадлежит 9 х Т или один из символов с, равен 7(ь, должны быть очевидны; оставляем их в качестве упражнения.
Р представляет собой сумму членов Р...и, = (Д+7р)'с с с, (Д+ф)Р~"'-'1(с с с,) (Д+ ф)' для всех с„с, и с, из д(1 (7Д, гдет(с,с,сз)=д (1 (Ф) — 1(с с сз). Ясно, что выражение Р имеет длину 0(р (и)) и его можно выписать за время 0(р(л)), где мультипликативная постоянная зависит лишь от М.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
