1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 81
Текст из файла (страница 81)
Мы исследуем также еще один класс задач, называемых "полными для полиномиальной емкости", которые по меньшей мере столь же сложны, как 1(Р-полные задачи, но и про них еще не доказано, что ааа 10.1. НЕДЕРТЕРМИНИРОВАННЫЕ МАШИНЫ ТЬЮРИНГА они трудно разрешимы. В гл. 11 будут изложены некоторые задачи, относительно которых действительно можно доказать, что они трудно разрешимы. 16.1. НЕДЕТЕРМИНИРОЕАННЫЕ МАШИНЫ ТЬЮРИНГА По причинам, которые скоро станут ясными, ключевое понятие в теории ХР-полных задач — недетерминированная машина Тьюринга '). Мы уже обсуждали недетермииированные конечные автоматы, у которых каждый шаг может перевести автомат в несколько различных состояний.
По аналогии недетерминироваииая машина Тьюринга имеет конечное число возможных шагов, из которых в очередной момент выбирается какой-то один. Входная цепочка х допускается, если по крайней мере одна последовательность шагов для входа х приводит к допускающему мгновенному описанию (МО). При данной входной цепочке х можно считать, что недетерминированная машина Тьюринга М параллельно выполняет все возможные последовательности шагов, пока не достигнет допускающего МО или пока не окажется, что дальнейшие шаги невозможны.
Иначе говоря, после 1' шагов можно считать, что существуют много экземпляров М. Каждый экземпляр представляет МО, в котором М может оказаться после 1 шагов. На (1+1)-м шаге экземпляр С порождает 1 своих экземпляров, если машина Тьюринга, находясь в МО С, может выбрать следующий шаг / способами. Таким образом, возможные последовательности шагов машины гИ на входе х можно организовать в виде дерева мгновенных описаний.
Каждый путь из корня в лист этого дерева представляет некоторую последовательность возможных шагов. Если о — кратчайшая последовательность шагов, которая оканчивается допускающим МО, то, как только машина М сделает 1о| шагов, она остановится и допустит вход х. Время, затрачиваемое на обработку входа к, равно длине последовательности о. Если на входе х никакая последовательность шагов не приводит к допускающему МО, то М отвергает х, а время, затрачиваемое на обработку х, не определено.
Часто удобно представлять себе, что М "угадывает" только шаги из последовательности о и проверяет, что о на самом деле оканчивается допускающим МО. Но поскольку детерминированная машина обычно не может заранее угадать допускающую последовательность шагов, то детерминированное моделирование машины М потребовало бы просмотра в некотором порядке дерева всех возможных последовательностей шагов на входе д и этот просмотр продал- жался бы до обнаружения кратчайшей последовательности, окан- Ч Чнтателю, недостаточно хорошо знакомому с машинами Тьюринга, предлагаем освежить в памяти равд.
Кб. ГЛ. ИХ МР-ПОЛНЫЕ ЗАДАЧИ чивающейся допускающим МО. Если никакая последовательность шагов не приводит к допусканию входа, то детерминированное моделирование машины М могло бы продолжаться бесконечно долго, если только нет какой-нибудь априорной границы на длину кратчайшей допускающей последовательности. Поэтому естественно ожидать, что недетерминированные машины Тьюринга способны выполнять задания, которые никакие детерминированные машины Тьюринга не могут выполнить за то же время или с той же памятью.
Тем не менее все еще открыт важный вопрос о существовании языков, допускаемых недетерминированной машиной Тьюринга с данной временной или емкостной сложностью, но не допускаемых никакой детерминированной машиной Тьюринга с той же сложностью. Определение. й-ленточной недетерминированной машиной Тьюринга (для краткости НМТ) М называют семерку (Я, Т, 1, 6, Ь, д„д,), где значения всех компонент те же, что и для обычной детерминированной машины Тьюринга, за исключением того, что здесь функция переходов 6 представляет собой отображение множества ДхТ' в множество подмножеств в Дх(Тх(1, К, З))А.
(1. означает сдвиг головки влево, К вЂ” вправо, Я вЂ” головка остается на месте.) Иными словами, по данному состоянию и списку из й ленточных символов функция 6 выдает конечное множество вариантов следующего шага; каждый вариант состоит из нового состояния, и новых ленточных символов и й сдвигов головок, Заметим, что НМТ М может выбрать любой из этих вариантов шага, но не может выбрать следующее состояние из одного шага, а новые ленточные символы — из другого или устроить какую-нибудь еще комбинацию вариантов шага. Мгновенные описания для НМТ определяются точно так же, как и для детерминированной машины Тьюринга (ДМТ). Данная НМТ М=(11, Т, 1, 6, Ь, д„д~) делает шаг, исходя из своего текущего состояния, скажем д, и сймволов, обозреваемых каждой из й головок, скажем Х„Х„..., Х„.
Из множества 6(а, Х„Х„..., Х„) она выбирает некоторый элемент (г, (Уи О,),..., (УА, Р,)). Этот элемент указывает, что новым состоянием должно стать г, на 1-й ленте следует напечатать 1', вместо Х, и головку сдвинуть в направлении, обозначенном знаком Ри 1~1(й. Если при некотором выборе следующего шага МО С переходит в МО Р, то пишут С) — „Р (или С) — О, если ясно, о какой машине М идет речь). Заметим, что для данной НМТ М может быть несколько таких О, что С ( — О, но если машина М детерминированна, то для каждого С существует не более одного такого Р.
Запись С,( — * С' означает, что для некоторого й выполняется С, ) — С, ) — ... 1 в С =С' или С,=С'. НМТ М допускает цепочку и, если (й.а, дм д„..., д,) )†*(а„ ссм..., аА), где а,(и, значит, ам ... !о.!. ннднтннмининовлннын млшины тьюпиигл ..., аз) содержит (где-то внутри себя) символ заключительногосостояния д,.
Языком 1. (М), допускаемым машиной М, называют множество всех цепочек, допускаемых М. Пример 1О,1. Построим НТМ, допускающую такие цепочки вида 10" 10"... 10 л, что ч ,', 11=~~„' 11 для некоторого множества lс:-(1, 2,..., и). Иными /ег уст словами, цепочка тв должна допускаться, если список ') целых чисел т,, г„..., г, представленный ею, можно разбить на два подсписка так, чтобы суммы чисел в них были равны. Эта задача известна как задача о разбиении. Доказано, что она ХР-полна, если целые числа 11 представлены своими двоичными кодами и размером задачи считается длина списка этих двоичных целых чисел *), Мы построим трехленточную НМТ М, распознающую этот язык. Она просматривает свою входную ленту слева направо, и каждый раз, когда она доходит до блока вида О!у, на вторую или третью ленту добавляются эти г; нулей, причем выбор ленты недетермини.
рован. После того как машина дойдет до конца входа, она проверит, совпадают ли числа нулей на лентах 2 и 3, и, если да, допустит вход. Поэтому, если какая-нибудь последовательность выборов, указывающая, в какое из множеств помещать очередное число гу — в первое (на ленту 2) или во второе (на ленту 3), приводит к равным суммам, то эта НТМ допустит вход. Последовательности шагов, приводящие к неравным цепочкам на лентах 2 и 3, не принимаются во внимание, если хотя бы одна последовательность выборов срабатывает, Формально пусть М ((уз~ уту уз)ч (0~ 1~ Ь~ $)> (О\ 1)~ б Ь уе~ уз)у где функция переходов б задана на рис.
10.1. На рис. !0.2 показаны две из многих последовательностей шагов, которые может сделать на входе 1010010 эта НМТ. Первая приводит к допускающему состоянию, вторая нет. Поскольку по крайней мере одна последовательность шагов приводит к допускающему состоянию, эта НМТ принимает 1010010. Д Определение. Говорят, что НМТ М имеет временную сложность Т(п), если для всякой допускаемой входной цепочки длины п найдется последовательность, состоящая не более чем из Т(п) шагов, ') Это список, а не множество из-за возможных повторений. е) Как мы увидим, способ кодированкя данных задачи очень важен.
Нетрудно показать, что если для распозианания используется дЫТ, то время решения задачи из примера !О.! составляет в действительности О (и'), где и — длина входа. Но если вход закодировать двоичными числами, то длина входа будет равна сумме логарифмов чисел 1„ ..., га и та же сгратегня даст алгоритм сложности О (с"), где и — зто уже длина двоичного входа и с>!. дау О, 11 Ь,В Ь,Ь ь,з Ь,Ь Ь,Е Машина переписывает блок из нулей на ленту 2, затем подостижении единицы на ленте 1 возвращается в состояние д,. Если же на ленте 1 достигнут символ Ь, она переходит в состояние о„ чтобы сравнить длины лент 2 и 3.
Ь Ъ Ь 0 1 Ь Машина допускает вход. Рис. 1О.1. Переходы [шаги) НМТ. Каждая строка представляет один вариант выбора. 1Он. НЕДЕТЕРМИНИРОВАННЫЕ МАШИНЫ ТЬЮРИНГА Рис. 10.2. Две возможные последовательности щагов длв НМТ, которая приводит в допускающее состояние, и едгкоалную сложность 5(а), если для всякой допускаемой входной цепочки длины л найдется последовательность шагов, приводящая в допускающее состояние, в которой число просмотренных головкой клеток на каждой ленте не превосходит Б(п). Пример 10.2.
НМТ из примера 10.1 имеет временную сложность 2а+2 (худший случай — вход из а единиц) и емкостную сложность И+1. Другие разумные кодирования задачи о разбиении также дают зту сложность. Например, пусть В (4) — двоичное представление целого числа 4 и 1, = (Ф В(4,) Ф В(1,) ..иЬВ(!А) ( существует такое множество (~(1,2, ...,Ц, что /44 14 1 где ~. — разделительный маркер. Чтобы распознать Ьи можно построить новую НМТ М„работа которой аналогична работе НМТ с рис. 10.1. Отличие состоит в том, что вместо копирования нулей на ленту 2 или 3 Мт запоминает на лентах двоичные числа.
Каждое новое двоичное число, встречающееся во входной цепочке, прибавляется к числу на той или другой ленте. (д,1010010, д„д,) 1 — (д,1010010, $ди $41,) (- (1 1,010010, $д„$Д,) ( — (10д,10010, $0д„$д,) ( — (1Одт10010, $041, $414) ! — (101д,0010, $0д„$д,) )- (10!Од,010, $0д„$0д,) ) — (101004),10, $0д„$ООд,) (- (1010041,10, $0д„$00д,) 1- (101001д,О, $0д„$00д,) >- (10100!Од„ $0041„ $00дз) (1010010444 $04440 $044 0) (1010010д4 $44400 $44400) ! — (10100!Од„д4$00, д4$00) ! — (10100!Од„д4$00, 414$00) Вход допускается <д,1010010, д„д,) ! — (е,1 010010, $В„$д,) ! — (1д,010010, $41„$д,) (- (10д,10010, $е„ $Од,) ( — (10д,!0010, $д„ $0д,) ! — (101д,0010, $д„ $0д,) (- (!0!Оп,О!О, $д„ $00д,) (- (10100д,(О, $д„ $ОООЕ,) ! — (101 ООд,10, $1„$000д,) (- (10!00141,0, $д,, $000д,) ( — (10100! Од„$д„$000041,) ! ( 1 01 001 0444 4)4$ $0004440) Остановка — нет следующего МО гл.
пс н»-полные з»д»чи Чтобы обработать список целых чисел 1„1„..., 1», машина М, просматривала бы входную цепочку х=ЯВ(1,)фВ(1»)...ДВ(ю»). Машина М при решении той же задачи просматривала бы входную цепочку гв=10п10'*...1О'», которая может оказаться экспонеициально длиннее цепочки х. Таким образом, хотя М, в некотором смысле экспоненциально быстрее, чем НМТ на рис. 10.1, ее временная и емкостная сложности, поскольку вход соответственно укорочен, все равно равны 0(п), где л — длина входа. С помощью моделирования можно показать, что любой язык, допускаемый какай-нибудь НМТ, допускается также и некоторой ДМТ, но за это, по-видимому, придется расплачиваться сильным увеличением временной сложности. Наименьшая верхняя граница, которую можно установить для такого моделирования, экспоненциальна.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
