Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 111
Текст из файла (страница 111)
МР-полные проблемы н со-МР Предположим, что Рх ЛР. Возможно, ситуация, связанная с со-ЛР, отличается от представленной иа рис. ) 1.1, поскольку ЛР и со-МР могут совпадать, ио быть больше Р. Таким образом, проблемы типа НВЫП или ТАВТ могли бы разрешаться за полииомиальиое иедетермииироваииое время, т.е. прииадпежать ЛT, ие имея детерминированного полииомиальиого решения. Однако отсутствие хотя бы одной ХР-полиой проблемы, имеющей дополнение в Л/)о, обосновывает, что ЛРх со-ЛР. Докажем это в следующей теореме. Теорема 11.2.
ЛР= со-ЛР тогда и только тогда, когда существует ХР-полиая проблема, дополнение которой принадлежит ЛГР. Доказательство. (Необходимость) Если бы ЛР и со-АгР совпадали, то каждая ХР- полная проблема Е находилась бы как в МР, так и в со-ЛР. Но дополнение проблемы из со-ЛР находится в /чР, поэтому дополнение Е принадлежало бы ЛР. 1Достаточность) Предположим, что Р— ХР-полиая проблема, дополиеиие Р которой принадлежит Л'Р.
Тогда для любого языка 1 из ЛР существует полииомиальиое све- 11.1. ДОПОЛНЕНИЯ ЯЗЫКОВ ИЗ ХР 483 дение Е к Р. Это сведение является одновременно полиномиальным сведением Х к Р . Докажем равенство классов ЛР и со-МР, показав их взаимное включение. МР ~ со-ЛР. Пусть Е принадлежит ЛР. Тогда Х принадлежит со-Л"Р. Объединим полиномиальное сведение Х к Р с предполагаемым недетерминированным полиномиальным алгоритмом для Р, чтобы получить такой же алгоритм для Х . Тогда для любого Х из ЛР его дополнение Х также принадлежит ЛР. Следовательно, Е, будучи дополнением языка из Л'Р, находится в со-ЛР.
Отсюда Л'Р с со-ЛР. Со-Л'Р с ЛР. Пусть Е принадлежит со-ЛР. Тогда существует полиномиальное сведение Х к Р, поскольку Р является 14Р-полным, а Х принадлежит Л'Р. Это сведение является также сведением Х к Р. Поскольку Р принадлежит ЛР, объединим это сведение с недетерминированным полиномиальным алгоритмом для Р и убедимся, что Х принад- лежит Л'Р. С) 11 1.3.
Упражнения к разделу 11.1 11Л.1. П) Ниже представлено несколько проблем. Для каждой определите, принадлежит она МР или со-АгР. Опишите дополнение каждой проблемы. Если проблема или ее дополнение являются )чР-полными, докажите зто. а) («) Проблема ИСТ-ВЫП. По данной булевой формуле Е, истинной, когда все переменные имеют значение "истина'*, определить, существует ли еще одна подстановка, удовлетворяю гцая Е. б) Проблема ЛОЖЬ-ВЫП. Дана булева формула Е, ложная, когда все переменные имеют значение "ложь". Определить, существует ли еще одна подстановка, при которой Е ложна.
в) Проблема ДВЕ-ВЫП. По данной булевой формуле Е определить, существуют ли хотя бы две подстановки, удовлетворяющие Е. г) Проблема ПОЧТИ-ТАВТ. Дана булева формула Е. Определить, является ли она ложной не более, чем при одной подстановке. 11.!.2. ~ «!) Предположим, что существует взаимно однозначная функция~; которая отображает одни л-битовые целые числа в другие и обладает следующими свойствами. 1. Ях) можно вычислить за полиномиальное время. 2. ~'(х) нельзя вычислить за полиномиальное время. Докажите, что в таком случае язык, состоящий из пар целых чисел (х, у), для которых г (х) <у, принадлежит (~ч'Р П со-ЛР) — 'Р. 484 ГЛАВА 11. ДОПОЛНИТЕЛЬНЫЕ КЛАССЫ ПРОБЛЕМ 11.2.
Проблемы, разрешимые в полиномиальном пространстве рассмотрим класс проблем, включающий уь'Р и, возможно, еще больше, но уверенности в этом нет. Этот класс определяется машинами Тьюринга, которые могут использовать объем пространства, полиномиальный относительно размера входа; время работы роли не играет. Вначале классы языков, допускаемых детерминированными и недетерминированными МТ с полиномиальным ограничением пространства, различаются, но затем будет показано, что они совпадают.
Для полиномиального пространства существуют полные проблемы Р в том смысле, что все проблемы данного класса сводимы за полиномиальное время к Р. Таким образом, если Р принадлежит Р или Л'Р, то все языки МТ с полииомиально ограниченным пространством также принадлежат Р или ЛР, соответственно. Мы представим пример такой проблемы — "булевы формулы с кванторами". 11.2.1, Машины Тьюринга с полиномиальным пространством Машина Тьюринга с полиномиальным ограничением пространства представлена на рис.
1 !.2. Сугцествует некоторый полинам р(и), для которого МТ, имея вход и длиной н, не посещает более р(п) клеток ленты. Согласно теореме 8.12 можно считать, что лента является односторонней, а МТ не сдвигается влево от начала входа. -т — входи — ил киеток р(и) кпеток Рис. 1!.2 МТ, исиольюуиияая полииомиальное иростраистио Класс языков Ро (ро1уиот!а! юрасе — полиномиальное пространство) определяется как множество языков ю'.(М) детерминированных МТ М с полиномиальио ограниченным пространством. Определим также класс ух'РБ (иоиг1егегт!ннйс ро!уиот!а! юрасе — иедетермииироваииое полиномиальное пространство) как множество языков 2.(М) недетерминированных МТ М с полиномиально ограниченным пространством.
Очевидно, Р$г МРБ, по- 11.2. ПРОБЛЕМЫ, РАЗРЕШИМЫЕ Б ПОЛИНОМИАЛЬНОМ ПРОСТРАНСТВЕ 485 скольку каждая детерминированная МТ является недетерминированной. Будет доказан не- ожиданный результат: РЯ = ЛРЯ.' 11.2.2. Связь РБ и Д(РЗ с определенными ранее классами Отметим сразу, что включения Р с 'РЯ и Л'Рс. Л'РЯ очевидны. Если МТ совершает полиномнальное число переходов, то она использует не более, чем полиномиальное число клеток, точнее, число посещаемых ею клеток не более, чем на 1 превышает число переходов.
Доказав, что РЯ = )з(РЯ, мы убедимся в справедливости цепочки вювочений Р ~ ЛР с РЯ. Существенное свойство МТ с полиномиально ограниченным пространством состоит в том, что они могут совершить не более, чем экспоненциальное число переходов перед повторением МО. Этот факт нужен для доказательства других интересных результатов, касающихся РЯ, а также для того„чтобы показать, что РЯ содержит только рекурсивные языки, т.е. языки с алгоритмами. Отметим, что в определении РЯ или Л'РЯ останов МТ не упоминается, т.е.
МТ может зацикливаться, не выходя за пределы полиномиальной по объему части ленты. Теорема 11.3. Если М вЂ” МТ с полиномиально ограниченным пространством, а р(л) — полиномиальный предел ее пространства, то существует константа с„при которой М, допуская свой вход и длиной л, делает это в пределах с ИМ переходов. Доказательство. Основная идея состоит в том, что М должна повторить МО перед тем, как совершить более с'чх"1 переходов. Если М повторяет МО и затем допускает, то должна существовать более короткая последовательность МО, ведущих к допусканию, т.е., ес- ли а ~- )З )- )) )- у где а — начальное,, — повторяемое, а у — допускающее МО, то а ~- )З ~- у — более короткая последовательность МО, приводящая к допусканию.
В обосновании существования с используется то, что у МТ с ограниченным пространством есть лишь ограниченное число МО. Точнее, пусты — число ленточных символов, а з — состояний МТ М. Тогда число различных МО М использующейр(л) клеток, не более зфл)гт'"з, т.е. можно выбрать одно из з состояний, поместить ленточную головку в одну из р(л) позиций и заполнить р(л) клеток любой из ГЯ'"1 последовательностей лен- точных символов. Выберем с = з + г и раскроем бином ( г+ з)" Ям; г'"~ич(1 ьр(л))земная ...
Заметим, что второе слагаемое не меньше зр(л)к"~; это доказывает, что с зз'ч не меньше числа возможных конфигураций М. Отметим, что, если М допускает вход ж длиной л, то она выполняет последовательность переходов без повторения МО. Следовательно, М допускает, совершив переходов не больше с'ин — количества различных МО. П ' Во многих работах этот класс обозначается Р8РЛСЕ.
Однако здесь ддя его обозначения применяется сокращение РЯ, достаточное ввиду установления равенства РЯ = ЛРЯ. ГЛАВА 11. ДОПОЛНИТЕНЬНЫЕ КЛАССЫ ПРОБЛЕМ 486 Теорему 11.3 можно использовать для преобразования любой МТ с полиномиально ограниченным пространством в эквивалентную машину, которая всегда останавливается, совершив не более экспоненциального числа переходов.
Зная, что МТ допускает в пре- делах экспоненциального числа переходов, можно подсчитать количество совершаемых переходов и остановить работу, не допуская, если сделано достаточно много переходов без допускания. Теорема 11.4. Если Ь вЂ” язык из РБ (МРо), то Т. допускается детерминированной (недетерминированной) МТ с полиномиально ограниченным пространством, которая для некоторого полинома д(п) и константы с останавливается после не более чем смм переходов. Доказательство.
Докажем утверждение для детерминированных МТ. Для НМТ доказательство аналогично. Пусть ь допускается МТ Мь имеющей полиномиальное ограничение пространства р(н). Тогда по теореме 11.3, если М, допускает и, то делает это в пределах с~ Н! !' шагов. Построим новую МТ М~ с двумя лентами. На первой ленте М, имитирует Мь а на втоРой ведет счет до с 'И!"!~, использУЯ основание с. Если счет У Мз достигает этого числа, то она останавливается, не допуская. Таким образом„М, использует 1 + р(~н !) клеток второй ленты.
Поскольку М~ использует не более р()н !) клеток своей ленты, М~ также использует не более р(~н4) клеток первой ленты. Преобразуя М, в одноленточную МТ Мз, можно гарантировать, что М, использует не более 1+р(п) клеток ленты при обработке любого входа длиной и. Хотя М, может использовать квадрат времени работы М„это время не превышает 0(с"'и).' МТ Мз совершает не более л!с~""' переходов для некоторой константы с( поэтому можно выбрать с(п) = 2р(л) ь 1ой,.
с( Тогда М, совершает не более с"'М шагов. М, всегда останавливается, поэтому то же делает Мз. М~ допускает ь, поэтому его же допускают Мэ и Мл Таким образом, Мз удовлетворяет утверждению теоремы. П 11.2.3. Детерминированное и недетерминированное полиномиальное пространство Сравнение классов Р и А)Р затруднительно, но, на удивление, сравнить классы РЯ и ЛРЯ легко — они совпадают.
Доказательство основано на имитации недетерминированной МТ, пространство которой ограничено полиномом р(п), с помощью детерминированной МТ, имеющей ограничение пространства 0(р(л)). ' В лействительнастн, общее правило из теоремы 8,!О не является сильнейшим утверждением, которое можно установить. Поскольку на любой ленте используется только ! + р(л) клеток, имитируемые головки при переходе от многих лент к одной не могут разойтись более, чем на ! + р(л) клеток. Таким образам, с "Ю! переходов многоленточнай МТ Мз можно праимитировать за 0(р(я)сЮ!) щагов, что меньше указанного 0(сзю!), 11.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
