Главная Промышленная автоматика.

Лита \ машины М

• • •

• • •

Головка на ленте 1

• « •

« « •

Лента 2 уашинв/ М

• •

• • a

Годовна на /тенте 2

• • •

• • •

Лента к машины М

• • *

• • •

Головка на ленте к

• • »

• • •

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

Лемма 10.1. Если язык L допускается k-ленточной НМТ М = = {Q, Т, I, б, Ь, 0, дд с временной сложностью Т{п), то он допускается одноленточной НМТ с временной сложностью 0{Т(п)).

Доказательство. Построим одноленточную НМТ Ali, допускающую L с временной сложностью 0{Т(п)). Представим себе (в соответствии с применяемой техникой моделирования), что лента машины Ml имеет 2k "дорожек" (рис. 10.4). Другими словами, ленточными символами машины Mi являются 2й-членные кортежи, в которых на нечетных местах стоят символы алфавита Т, а на четных - либо символ пробела Ь, либо специальный маркер #. Дорожки с нечетными номерами соответствуют k лентам машины М, а каждая дорожка с четным номером содержит символ b во всех клетках, кроме одной, в которой стоит #. Символ # на дорожке с номером 2/ отмечает положение головки машины М на ленте /, которой соответствует дорожка с номером 2/-1. На рис. 10.4 головка /-Й ленты обозревает клетку ij на /-й ленте для всех /, 1/Л,

Ml моделирует один шаг машины М следующим образом. Предположим, что вначале головка машины Mi обозревает клетку, содержащую самую левую головку машины М.

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

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



ШИНОЙ М, которые Mi также нашла, машина Mi недетерминированно выбирает возможный шаг для М. Для каждого шага, возможного для М в этой ситуации, машина Mi имеет состояние, в которое может перейти на следующем шаге. 3. Выбрав для моделирования шаг машины М, машина Mi изменяет в соответствии с ним состояние машины М, которое она помнит в своем состоянии. Затем Mi сдвигает свою головку влево, пока не пройдет через все k маркеров головок. Всякий раз, когда Mi находит такой маркер, она изменяет ленточный символ, стоящий на дорожке над маркером, и сдвигает этот маркер не более чем на одну клетку влево или вправо в соответствии с выбранным шагом.

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

Ml может допустить вход, когда его допускает М, поскольку Mi помнит состояние машины М. Если М допускает цепочку w длины п, то делает это с помощью последовательности, состоящей не более чем из Т(п) шагов. Очевидно, в последовательности из Т{п) шагов головки машины М не могут разойтись больше, чем на Т (п) клеток, и, значит. Ml может смоделировать один шаг этой последовательности не более чем за 0{Т(п)) своих шагов. Таким образом. Mi допускает цепочку W, выполняя не более 0{Т (п)) шагов. Отсюда следует, что Ml допускает язык L и имеет временную сложность 0{ТЦп)). а

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

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

Следствие 2. Если язык L допускается k-ленточной НМТ с емкостной сложностью S{n), то он допускается одноленточной НМТ с емкостной сложностью S(n).

Следствие 3. Если язык L допускается k-ленточной ДМТ с емкостной сложностью S (л), то он допускается одноленточной ДМТ с емкостной сложностью S{n).

10.2. КЛАССЫ 5» И оЛГ5»

Введем два важных класса языков.

Определение. Определим Э-ТШЕ как множество всех языков, допускаемых ДМТ с полиномиальной временной сложностью, т. е.



5*-Т1МЕ = {LI существуют такие ДМТ М и полином р(«). что временная сложность машины М равна р{п) и L(M) = L}.

Определим сЛГ-ТШЕ как множество всех языков, допускаемых НМТ с полиномиальной временной сложностью. Для краткости мы будем часто писать и оЛГ* вместо 5*-Т1МЕ и (JfS-TlfAE соответственно.

Прежде всего заметим, что, хотя классы 5* и сЛГ* определены в терминах машин Тьюринга, можно было бы использовать любую из многих других моделей вычислений. Интуитивно можно представлять себе 5 как класс языков, распознаваемых за полиномиальное время. Например, мы показали, что если язык L допускается машиной Тьюринга с временной сложностью Т{п), то временная сложность его распознавания на РАМ или РАСП при логарифмическом весовом критерии будет лежать между kiT{n) и кТф), где ki и /г2 - некоторые положительные постоянные. Таким образом, язык L допускается машиной Тьюринга с полиномиальной временной сложностью тогда и только тогда, когда существует алгоритм его распознавания, реализуемый на РАМ или РАСП с полиномиальной сложностью при логарифмическом весовом критерии.

Можно также определить недетерминированную РАМ или РАСП, добавив к системе команд команду CHOICE(Li, L,. . ., L), означающую, что недетерминированны выбор и последующее выполнение одного из операторов Li, L2,. . ., L. Таким образом, класс ojT5* можно также определить с помощью недетерминированных РАМ или РАСП с полиномиально ограниченной временной сложностью при логарифмическом весовом критерии.

Следовательно, можно представить себе недетерминированную вычислительную машину вроде РАМ или РАСП, способную вьшолнить много различных возможных последовательностей шагов, начинающихся с данного МО. Оказывается, такое устройство может распознать за полиномиальное время многие языки, по-видимо.му нераспознаваемые за полиномиальное время детерминированными алгоритмами. Разумеется, любая попытка прямого моделирования недетерминированного устройства детерминированным устройством D, выполняющим все возможные последовательности шагов, занимает гораздо больше времени, чем любая единичная реализация последовательности шагов устройства Л, поскольку D должно прослеживать работу огромного количества копий N. На основе результатов предыдущего раздела мы можем утверждать лишь, что если язык L принадлежит ЖЗ, то он допускается некоторой ДМТ с временной сложностью kP"\ где k - постоянная и р - полином, зависящие от L.

С другой стороны, еще никому не удалось доказать, что существует язык из qMS, не принадлежащий 5. Таким образом, неизвестно, является ли 5* собственным подклассом класса JfS. Однако можно





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 [134] 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0029