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