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

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

Вспомним, что по теореме 10.1, если допускается некоторой НМТ с емкостной сложностью где полином, то он допускается некоторой ДМТ с емкостной сложностью Поэтому включает в себя также все языки, допускаемые НМТ с полиномиально ограниченной памятью. Так как каждая НМТ с полиномиально ограниченным временем имеет полиномиально ограниченную память, ясно, что (рис. 10.13). Кроме того, поскольку то из равенства следует, что а потому распознавание детерминированным алгоритмом с полиномиально ограниченным временем работы любого языка из еще менее вероятно, чем распознавание таким алгоритмом любого языка из

Можно указать довольно естественный язык полный для Так называется язык, который принадлежит и удовлетворяет следующему условию: если он допускается какой-то детерминированной МТ с ограниченным функцией временем работы, то для каждого языка найдется детерминированная МТ с временем работы, ограниченным функцией где полином, зависящий от (Здесь слово "детерминированная" можно заменить на "недетерминированная".) Поэтому если то Если то Язык это множество регулярных выражений, дополнения которых представляют непустые множества.

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

Лемма 10.2. Пусть - одноленточная ДМТ с памятью, ограниченной полиномом Тогда найдется такой полином что если то за время можно построить регулярное выражение дополнение которого представляет пустое множество тогда и только тогда, когда не допускает х.

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

Регулярное выражение можно представлять себе как способ описания последовательностей МО машины которые не допускают цепочку х. Для наших целей понадобится алфавит Символ из представляет клетку входной ленты машины обозреваемую головкой, причем клетка содержит X, а находится в состоянии Если допускает х, то в соответствующей последовательности шагов на каждом шаге используется не более клеток на ленте. Поэтому можно представлять МО цепочкой состоящей ровно из символов, причем все они, кроме одного, взяты из этот один символ имеет вид Последовательность шагов машины можно представить цепочкой для некоторого где новый разделительный символ и каждая цепочка из А представляет некоторое При необходимости в это МО добавляются пустые символы (чтобы сделать длину цепочки равной

Мы хотим построить регулярное выражение так, чтобы оно представляло те цепочки из которые не описывают допускающие вычисления машины для входа х. Поэтому будет представлять все цепочки из тогда и только тогда, когда не допускает х. Цепочка не будет представлять допускающее вычисление машины только тогда, когда выполнено одно или более из следующих четырех условий. Мы считаем, что

1. Цепочка у ни для какого не имеет вида где для каждого и все символы цепочки принадлежат за исключением одного, который имеет вид

2. Начальное неправильно, т. е. цепочка у не начинается с где а число пустых символов равно

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

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

будет иметь вид где регулярные выражения, представляющие множества, определяемые условиями 1—4 соответственно.

Полезно ввести сокращения для записи регулярных выражений. Если мы пользуемся алфавитом то будет обозначать регулярное выражение регулярное выражение раз), т. е. цепочки длины в алфавите Заметим, что длина регулярного выражения, обозначенного через равна а через равна Аналогично, если то будет обозначать регулярное выражение

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

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

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

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

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

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

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

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

Остальные слагаемые определяются равенствами и в совокупности представляют множество цепочек, содержащих менее символов из А между двумя символами

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

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

2, 3 или 4, но нарушают условие 1, т. е. цепочки вида где Однако для простоты мы выпишем выражения, определяющие множества цепочек, которые удовлетворяют условию 2, 3 или 4 и нарушают условие 1, а также некоторых цепочек, удовлетворяющих не только условию 2, 3 или 4, но и условию 1. Так как цепочки последнего типа уже представлены в в силу определения выражения А, их наличие или отсутствие в несущественно.

Считая, что входная цепочка имеет вид полагаем где

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

Положим Длина этого выражения, конечно, зависит только от

Наконец, построим Пусть дана цепочка у, представляющая правильное (т. е. позволяющее фактически реализовать) вычисление машины Тогда у имеет вид где для каждого это МО, которое получается из за один шаг работы машины Заметим, что по данным трем последовательным символам цепочки у можно однозначно определить символ, назовем его который должен появиться в цепочке на символов правее Например, если все принадлежат то не может измениться в следующем МО, так что Если принадлежат символ из то Остальные правила для определения включая те, что соответствуют случаю, когда или принадлежит или один из символов равен должны быть очевидны; оставляем их в качестве упражнения.

D представляет собой сумму членов

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

Таким образом, регулярное выражение можно построить за время где полином, растущий по порядку как Более того, представляет множество тогда и только тогда, когда х не допускается машиной

Итак, в лемме 10.2 построено регулярное выражение над алфавитом размер которого зависит от Мы хотим рассуждать о "языке регулярных выражений, дополнения которых (относительно их алфавитов) представляют непустые множества". Так как язык должен определяться над конечным алфавитом, мы будем кодировать регулярное выражение над конечным алфавитом 2 следующим образом:

1) ей скобки обозначают сами себя,

2) t-й символ алфавита (в произвольном порядке) обозначается через где десятичное представление числа

Таким образом, для кодирования любого регулярного выражения над любым алфавитом достаточно 17 символов из алфавита

Определим язык как множество кодов тех регулярных выражений дополнения которых представляют непустые множества. Если выражение над алфавитом 2, то дополнение берется относительно Заметим, что если выражение имеет длину то длина его кода не превосходит

Лемма принадлежит классу

Доказательство. По теореме 10.1 достаточно построить которая допускает язык работая с полиномиально ограниченной памятью. регулярное выражение, код которого подан на вход машины В силу теоремы 9.2 по данному регулярному выражению длины можно построить недетерминированный конечный автомат с не более чем состояниями, распознающий язык, представленный этим регулярным выражением. сначала строит автомат А по коду выражения поданному машине Заметим, что по теореме 9.2 можно построить функцию переходов автомата А за время, не превосходящее

Допустим, что дополнение множества, представленного выражением непусто. Тогда существует цепочка не принадлежащая языку, представленному выражением угадывает ее символ за символом. Для хранения множества состояний, в которых А может оказаться после прочтения машина использует массив из битов. Она начинает с множества состояний, достижцмых из начального состояния автомата А только с помощью -переходов. После того как она угадает автомат А может находиться в одном из состояний множества Когда угадывает следующий входной символ она прежде всего вычисляет где — функция переходов автомата А, а затем строит добавляя к все состояния из для из (Обратите внимание на аналогию с алгоритмом 9.1.)

Когда угадает она выяснит, что не содержит заключительного состояния автомата А. Обнаружив это, машина допускает свой вход, т. е. код регулярного выражения Таким образом, допускает код выражения тогда и только тогда, когда дополнение множества, представленного выражением непусто.

Теперь покажем, что язык состоящий из кодов тех регулярных выражений, которые представляют множества с непустыми дополнениями, полон для полиномиальной памяти.

Теорема 10.14. Если допускается ДМТ с временной сложностью для каждого найдется такой полином что допускается за время

Доказательство. Пусть будет ДМТ, допускающей . В силу леммы 10.2 и рассуждений, проведенных выше, существует алгоритм с полиномиально ограниченным временем работы, скажем с временной сложностью который по входной цепочке х строит регулярное выражение Это выражение в фиксированном -символьном алфавите, и, разумеется, оно не длиннее По лемме 10.2 его дополнение пусто тогда и только тогда, когда По предположению можно проверить пустоту этого дополнения за шагов. Построение занимает шагов, а проверка пустоты — шагов. Так как то для завершения доказательства достаточно взять

Следствие. принадлежит тогда и только тогда, когда

Доказательство. Если то принадлежит по лемме 10.3. Обратное следует из теоремы 10.14 с полиномиальной функцией

Теорема 10.15. Если допускается НМТ с временной сложностью то для каждого найдется такой полином что допускается НМТ за время

Доказательство. Аналогично доказательству теоремы 10.14.

Следствие. принадлежит тогда и только тогда, когда

УПРАЖНЕНИЯ

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

Замечания по литературе

Дополнительную информацию о недетерминированных машинах Тьюринга можно найти в книге Хопкрофта, Ульмана [1969]. Теорему 10.1, устанавливающую связь между емкостными сложностями детерминированных и недетерминированных машин, доказал Сэвич [1970].

Ключевая теорема о NP-полноте задачи выполнимости принадлежит Куку 119716]. Много классических NP-полных задач привел Карп [1972], ясно продемонстрировав важность понятия NP-полноты. С тех пор к семейству известных NP-полных задач были добавлены новые, найденные Сахни [1972], Сети [1973], Ульманом [1973], Раундзом [1973], Ибаррой, Сахни [1973], Хантом, Розенкранцем [1974], Гэри, Джонсоном, Стокмейером [1974], Бруно, Сети [1974] и многими другими. Интересно, что до Кука в нескольких работах была показана полиномиальная взаимосвязь между некоторыми NP-полными задачами, но объем всего класса не был осознан. Например, Данциг, Блаттнер, Рао [1966] установили связь между задачами о коммивояжере и о кратчайшем пути с неотрицательными весами. Диветти, Грасселли [1968] описали связь между задачами о покрытии множествами и о множестве ребер, разрезающих циклы.

Задачи, полные для впервые рассмотрели Мейер, Стокмейер [1972]. Первый язык, полный для памяти, неявно описал Сэвич [1971], определив язык (множество проходимых лабиринтов), полный для -памяти. Джоунс [1973] и Стокмейер, Мейер [1973] рассмотрели ограниченные формы сводимости задач за полиномиальное время. Бук [1972, 1974] доказал несравнимость некоторых классов сложности.

Упр. 10.8 и 10.9 взяты у Кука [19716], упр. 10.10 и 10.12 — у Карпа [1972], упр. 10.13 — у Стокмейера, Мейера [1973] и Ханта [1973а], упр. 10.14 и 10.28- у Стокмейера, Мейера [1973], а упр. 10.15-10.18 - у Гэри, Джонсона, Стокмейера [1974]; рис. 10.14 представляет собой улучшенный вариант, предложенный Фишером. Доказательство NP-полноты задачи -раскрашиваемости пленарных графов появилось в работе Стокмейера [1973]. Упр. 10.20 заимствовано из работы Ивена [1973], упр. 10.21 — Ульмана [1973], упр. 10.25 — Кука [19716], а редукция, нужная для решения упр. 10.27, взята у Карпа [1972]. Доказательство теоремы 10.13 предложил нам Ивен.