Методические указания к курсу ”Сложность вычислений” (стр. 3 )

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

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

  Обозначим  через  L(M)  множество  всех  слов  ω∈X*,  допускаемых  машиной  M,  L(M)  называют  языком  машины  M.

Теорема.  Если  M  недетерминированная  машина  с  полиномиальной  временной  сложностью  T(n),  то  существует  детерминированная  машина  M ’,  с  L(M ’ ) = L(M)  и  временной  сложностью  O(cT(n)).

Доказательство. Доказательство  основывается  на  том,  что  для  любой  недетерминированной  машины  Тьюринга  M  строится  детерминированная  машина  M ’,  которая  исследует  последовательности  конфигураций (пути  в  дереве  недетерминированной  машины)  и  если  находит  хотя  бы  одну  с  допускаемым  состоянием,  то  сама  переходит  в  допускаемое  состояние.  Обследованные  конфигурации  помещаются  в  очередь,  длины  k  (k=1,2…) Построим  детерминированную  многоленточную  машину  M ’, моделирующую  недетерминированную  машину  M. Первая  лента  машины M ’ хранит  последовательность  конфигураций  машины  M  и  метку  на  текущее  состояние  последней.  Записи  слева  от  метки  предполагаются  исследованными  и  их  в  дальнейшем  игнорируют.  Конфигурации  справа  рассматриваются  в  порядке  очереди.  Программа  машины  M  хранится  в  конечном  управлении  M ’.  Обработка  текущей  конфигурации  на  первой  ленте  состоит  в  следующем:

- Машина  M ’  проверяет  состояние  и  обозреваемый  символ  и,  если  состояние  допускающее,  также  переходит  в  допускающее  состояние.

- Если  состояние  не  допускающее  и  из  данной  конфигурации  есть  k  переходов,  то M ’  использует  вторую  ленту  для  создания  k  копий,  которые  записываются  в  конце  очереди  на  ленте 1. 

- M ’ изменяет  k  конфигураций  в  соответствии  с  программой  машины  M.

- M ’  перемещает  отметку  текущей  конфигурации  на  следующую  справа  и  цикл  повторяется  с  шага 1.

Допустим,  что  m  есть  максимальное  число  выборов  машины  M  в  любой  конфигурации.  Тогда  существует  одно  начальное  состояние  M,  не  более  m  конфигураций,  достижимых  за  1 шаг, не  более  m2  конфигураций,  достижимых  за  2 шага  и  т. д.  Таким  образом,  после  n  переходов машина  M  может  достичь  не  более  1+ m +m2 +…+mn  ≤  n⋅mn  конфигураций.  Порядок,  в  котором  машина M ’  исследует  конфигурации,  называется  “поиском  в  ширину”,  т. е. M ’  исследует  все достижимые конфигурации  машины  M за  0 шагов,  достижимые  за  1 шаг  и  т. д. 

Допускающая  конфигурация  машины  M  будет  рассмотрена  машиной  M ’  в  числе  первых  n⋅mn  конфигураций.  Таким  образом,  если  машина  M  допускает,  то  машина M ’  также  допускает,  т. е.  L(M) = L(M ’ ).

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

Теорема. Если  M  недетерминированная  машина  Тьюринга  с  емкостной  сложностью  S(n),  то  найдется  детерминированная  машина  Тьюринга  M’  с  емкостной  сложностью  O(S2(n))  и  L(M’ ) = L(M). 

Доказательство. Пусть  M  недетерминированная  машина  Тьюринга  (возможно  k-ленточная)  с  емкостной  сложностью  S(n).  Тогда  число  различных  конфигураций,  в  которые  машина  M  может  попасть  из  начальной  с  входом  длины  n,  не  превосходит  некоторого  числа  cS(n),  точнее  |Q|(|X|+1)k S(n) (S(n))k,  где  k – число  лент.  Тогда  число  переходов  от  конфигурации  C1  к  конфигурации  C2  (С1├ С2)  на  любой  из  лент  не  превосходит  cS(n) .  Можно  выяснить,  существует  ли  переход  С1├ С2  за  2i  шагов,  проверив  для  всех  C3  существует  ли  переход С1├ С3  и С 3├ С2  за  i  шагов. После  каждого  обращения  к  процедуре  число  i  уменьшается  вдвое.

  Идея  моделирования  машиной  M’  работы  машины  M  приведена  в  доказательстве  предыдущей  теоремы.  Стратегия  работы  машины  M’  -

установить  приведет  ли  начальная  конфигурация  C0  к  какой-нибудь  допускающей  конфигурации  Cf  . Чтобы  найти  верхнюю  емкостную  границу  для  машины  M’,  расположим  конфигурации  (длины  O(S(n)))  на  стеках  того  же  размера.  В каждый  момент  времени  число  фрагментов  стека  не  превосходит  1+ log ⎡cS(n)⎤ , т. е.  O(S(n)).  Для  всего  стека  машины  M  потребуется  O(S2 (n))  ячеек.

Теорема. Если  язык  L  допускается  k-ленточной  недетерминированной  машиной  Тьюринга  M = (X, Q, q0, F, I)  с  временной  сложностью  T(n),  то  он  допускается  одноленточной  недетерминированной  машиной  с  временной  сложностью  O(T2(n)).

Доказательство.  Пусть  M1  одноленточная  недетерминированная  машина  Тьюринга,  имеющая  на  ленте  2k  дорожек,  т. е.  ленточные  символы  машины  M1  представляются  2k-членными  кортежами,  в  которых  на  нечетных  местах  стоят  символы  алфавита  X,  а  на  четных – либо  символ  Λ,  либо  маркер  #.  Дорожки  с  нечетными  номерами  соответствуют  k  лентам  машины  M,  а  каждая  дорожка  с  четным  номером  2j  содержит  символ  Λ  во  всех  ячейках,  кроме  одной,  где  стоит  маркер  #,  отмечающий  положение  головки  машины  M  на  ленте  j,  которой  соответствует  дорожка  2j-1.  Машина  M1  моделирует  один  шаг  работы  машины  M  следующим  образом.  Допустим, что  вначале  головка  машины  M1  обозревает  клетку,  содержащую  самую  левую  головку  машины  M. 

Головка  машины  M1  движется  вправо,  пока  не  минует  все  k  маркеров  положений  головок  на  дорожках  с  четными  номерами.  При  этом  M1  запоминает  в  своем  состоянии  символы,  обозреваемые  каждой  из  головок  машины  M. Теперь  M1  делает  недетерминированное  развлетвление,  исходя  из  состояния  машины  M,  которое  машина  M1  запомнила  в  своем  состоянии,  и  обозреваемых  машиной  M  на  лентах  символов,  которые  машина  M1  также  нашла. Выбрав  для  моделирования  шаг  машины  M,  машина  M1  изменяет  в  соответствии  с  ним  состояние  машины  M,  которое  она  помнит  в  своем  состоянии.  Затем  M1  сдвигает  свою  головку  влево  и проходит  все  маркеры,  изменяя  ленточный  символ  на  дорожке  над  маркером  и  сдвигая  маркер не  более  чем  на  одну  клетку (L, R,S). 

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