10.1. НЕДЕТЕРМИНИРОВАННЫЕ МАШИНЫ ТЬЮРИНГА

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

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

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

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

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

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

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

Запись означает, что для некоторого к выполняется или допускает цепочку если значит,

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

Пример 10.1. Построим НТМ, допускающую такие цепочки вида

что для некоторого множества Иными словами, цепочка должна допускаться, если список целых чисел представленный ею, можно разбить на два подсписка так, чтобы суммы чисел в них были равны. Эта задача известна как задача о разбиении. Доказано, что она NP-полна, если целые числа представлены своими двоичными кодами и размером задачи считается длина списка этих двоичных целых чисел.

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

где функция переходов задана на рис. 10.1.

На рис. 10.2 показаны две из многих последовательностей шагов, которые может сделать на входе 1010010 эта НМТ. Первая приводит к допускающему состоянию, вторая нет. Поскольку по крайней мере одна последовательность шагов приводит к допускающему состоянию, эта НМТ принимает 1010010.

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

(см. скан)

Рис. 10.2. Две возможные последовательности шагов для НМТ.

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

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

где разделительный маркер. Чтобы распознать можно построить новую работа которой аналогична работе НМТ с рис. 10.1. Отличие состоит в том, что вместо копирования нулей на ленту 2 или запоминает на лентах двоичные числа. Каждое новое двоичное число, встречающееся во входной цепочке, прибавляется к числу на той или другой ленте.

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

С помощью моделирования можно показать, что любой язык, допускаемый какой-нибудь НМТ, допускается также и некоторой ДМТ, но за это, по-видимому, придется расплачиваться сильным увеличением временной сложности. Наименьшая верхняя граница, которую можно установить для такого моделирования, экспоненциальна. Другими словами, если разумная функция, задающая временную сложность (разумная в том смысле, что она "конструируема по времени", этот термин определяется в гл. 11), то для каждой НМТ М, время работы которой ограничено функцией можно найти такие постоянную что и время работы машины составляет

Этот результат можно доказать, построив моделирующую машину путем полного перебора возможных вычислений. Существует постоянная ограничивающая число выборов очередного шага машины во всех ситуациях. Поэтому последовательность, содержащую вплоть до шагов работы машины можно представить цепочкой в алфавите длина которой не превосходит моделирует поведение машины на входе х длины следующим образом. последовательно порождает в лексикографическом порядке все цепочки из 2, длины которых не превосходят Таких цепочек не более Когда новая цепочка порождена, машина моделирует последовательность шагов машины представленную цепочкой Если приводит к тому, что допускает х, то также допускает х. Если не представляет возможную последовательность шагов машины или не приводит к допусканию х машиной то повторяет этот процесс со следующей цепочкой из 2.

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

Следует, однако, подчеркнуть, что не известно никаких нетривиальных нижних оценок, касающихся сложности моделирования НМТ с помощью ДМТ. А именно не известен никакой язык который может допустить какая-то НМТ с временной сложностью

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

Определение. Функцию назовем конструируемой по емкости (памяти), если некоторая ДМТ М, начав работу над данным входом длины поместит специальный маркер на клетку одной из своих лент, просмотрев не более клеток на каждой ленте. Самые обычные функции, например полиномы с целыми коэффициентами, конструируемы по емкости.

Можно показать, что если конструируемая по емкости функция, с емкостной сложностью, ограниченной функцией то найдется такая ДМТ М с емкостной сложностью что

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

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

Алгоритм 10.1. Детерминированное моделирование НМТ

Вход. НМТ М с границей на емкостную сложность, где конструируемая по емкости функция, и входная цепочка длины

Выход. "Да", если и "нет" в противном случае.

Метод. Рекурсивная процедура приведенная на рис. 10.3, распознает, осуществим ли переход за шагов. Если да, то она принимает значение true, в противном случае false. В этом алгоритме обозначают МО, в которых на каждой ленте использовано не более клеток.

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

Рис. 10.3. Процедура ПРОВЕРКА.

вызовов выдал значение true, то ответом алгоритма будет "да", в противном случае "нет".

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

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

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

Рис. 10.4. Лента машины

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

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

1. Головка машины движется вправо, пока не минует все маркеров положений головок на дорожках с четными номерами. Во время этого движения запоминает в своем состоянии символы, обозреваемые каждой из головок машины М.

2. Действия машины на шаге 1 детерминированны. Теперь делает недетерминированное "разветвление". А именно, исходя из состояния машины которое машина запомнила в своем состоянии, и из символов на лентах, обозреваемых

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

3. Выбрав для моделирования шаг машины машина изменяет в соответствии с ним состояние машины которое она помнит в своем состоянии. Затем сдвигает свою головку влево, пока не пройдет через все маркеров головок. Всякий раз, когда находит такой маркер, она изменяет ленточный символ, стоящий на дорожке над маркером, и сдвигает этот маркер не более чем на одну клетку влево или вправо в соответствии с выбранным шагом.

В этот момент машина промоделировала один шаг работы Ее головка находится правее левого маркера головок не больше чем на две клетки, так что можно найти этот маркер и повторить цикл.

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

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

Доказательство. Если в приведенном выше доказательстве машина детерминированна, то тоже будет детерминированной.

Следствие 2. Если язык допускается -ленточной НМТ с емкостной сложностью то он допускается одноленточной НМТ с емкостной сложностью

Следствие 3. Если язык допускается -ленточной ДМТ с емкостной сложностью то он допускается одноленточной ДМТ с емкостной сложностью