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