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

w ∈ L(M). 

  Для  записи  E  потребуется  ввести  полиномиальное  число  переменных  yj A,  утверждающих,  что  j-я  позиция  представляемого  МО содержит  символ  A – ленточный  или  состояние  M (j  может  изменяться  от  0  до  p(n)). 

Предположим,  что  пропозициональные  переменные  разных  МО  различны. Но  поскольку  разных  МО  полиномиальное  число,  общее  количество  пропозициональных  переменных  полиномиально. 

  Обозначим  кванторную  приставку  (∃x1∃x2…∃xm),  где  x1, x2,…,xm – все  пропозициональные  переменны  МО  I  как  (∃I);  аналогично  для  квантора  всеобщности – (∀).  КБФ  примет  вид :  (∃I0) (∃If) (S & N & F),  где

I0  и  If  -  переменные  МО,  представляющие  начальное  и  допускающее  М,  соответственно. S – выражение,  говорящее,  что  I0  является  начальным  МО машины  M  на  входе  w. N – выражение,  говорящее  о  переходах  M  при  преобразовании  I0  к  If. F – выражение,  говорящее,  что  If  является  допускающим  МО.

О  каждой  формуле  в  деталях:

  S – конъюнкция  литералов;  каждый  литерал – одна  из  переменных  МО.  Литерал  yj A  входит  в  I0 ,  если  в  j-й  позиции  начального  МО  с  входом  w  находится  символ  A,  в  противном  случае  в  I0  входит ¬ yj A.

Таким  образом,  если  w = a 1a 2…a n,  то  без  отрицания  в  МО  I0  входят  y0q 0 ,  y1a1 , y2a2 ,…, ynan  и  все  yj B  для  j = n+1, n+2,…, p(n),  где  q0 – начальное  состояние  и  B = Λ,  а  все  остальные  переменные  МО  I0  -  с  отрицаниями.

  If  -  допускающее  МО,  если  содержит  заключительное (допускающее)  состояние.  F – дизъюнкция  переменных  yj A,  выбранных  из  пропозициональных  переменных  МО  If,  для  которых  A  является  допускающим  состоянием.  Позиция  j  произвольна. 

  N – строится  с  помощью  метода,  позволяющего  удвоить  число  рассматриваемых  переходов,  добавив  лишь  O(p(n))  символов  и  затратив  O(p(n))  времени. Равенством  I = J  обозначим  конъюнкцию  выражений

  ( yj A z j A +  ¬ yj A  ¬ z j A),  где  j  изменяется  от  0  до  p(n),  а  A – любой  ленточный  символ  или  состояние  M,  МО  I  состоит  из  переменных  yj A  и

J -  из  переменных  z j A.

  Ni (I, J)  -  означает, что  переход  от  МО  I  к  МО  J  занимает  не  более  i  переходов,  обозначается  I ├  i  J,  i = 1,2,4,… .  В  этих  выражениях  свободны  только  переменные  I  и  J,  остальные  переменные  связаны. 

Базис.  Для  i = 1  выражение  Ni (I, J)  устанавливает,  что  I = J или I ├  1  J,  т. е.  N1(I, J)  есть  дизъюнкция  этих  утверждений. N1 (I, J)  записывается  за  время  O(p(n)).

Индукционный  шаг.  По  Ni  строим  N2i.  Корректный  способ  записи  N2i  состоит  в  том,  чтобы  в  выражении  записывать  одну  копию  Ni,  подставляя  как  (I, K),  так  и  (K, J)  в  одно  и  то  же  выражение.  Таким  образом,  в  N2i  (I, J)  используется  одно  подвыражение  Ni (P, Q).  N2i (I, J) утверждает,  что  существует  МО  K,  при  котором  для  всех  МО  P  и  Q  выполняется  хотя  бы  одно  из  следующих  условий :

1)  (P, Q) ≠ (I, K)  и  (P, Q) ≠ (K, J);  2)  Ni (P, Q)  -  истинно.

Иными  словами,  Ni (I, K)  и  Ni (K, J)  истинны,  а  для  других  пар  МО

(P, Q)  истинность  Ni (P, Q)  не  имеет  значения. Итак,  КБФ  имеет  вид : 

N2i  (I, J) = (∃K)(∀P)(∀Q)(N i  (P, Q) ∨ (¬ (I = P & K = Q) & ¬ (K = P & J = Q))).

На  запись  N2i  (I, J)  уходит  время,  необходимое  для  записи  N i,  а  также  O(p(n))  для  дополнительной  работы. 

  Чтобы  завершить  построение  N,  нужно  записать  Nm  для  наименьшего  m, которое  является  степенью 2  и  не  меньше  c1+ p(n) – максимально  возможного  числа  переходов, совершаемых  M  до  заключительного (допуска - ющего)  состояния.  Количество  применений  шага  индукции,  описанного  выше,  равно  log2 (c1+ p (n) ),  или  O(p(n)).  Поскольку  каждое  исполнение  шага  индукции  требует O(p(n))  времени, то  N  строится за  время  O(p2(n)).

Завершение  доказательства  теоремы. Выше  было показано,  как  преобразовать  вход  w  в  КБФ  -  (∃I0) (∃If) (S & N & F)  за  время,  полиномиальное  относительно  ⎜w⎟.  Было  доказано,  что  выражения  S, N, F  -  истинны  тогда  и  только  тогда,  когда  их  свободные  переменные  представляют  МО  I0  и  If,  являющиеся  соответственно  начальным  и  заключительным  МО  в  вычислениях  машины  M  на  входе  w.  Таким  образом,  данная  КБФ имеет  значение  1  тогда  и  только  тогда,  когда  M  допускает  w.

Классы  языков,  основанные  на  рандомизации

  Вероятностная  машина  отличается  от  детерминированной  тем,  что  в  левой  части  инструкции  появляется  еще  один  символ  - выходное  значение  датчика  случайных  чисел  с  конечным  алфавитом,  который  на  каждом  шаге  работы  выдает  свои  значения  равновероятно  и  независимо  от  значений,  выданных  на  других  шагах.  Вероятность  “p”  вычисления  на  вероятностной  машине  на  входе  “x”  результата  “y” равна  сумме  вероятностей  всех  реализаций  “y”  на  входе  “x”.  Говорят,  что  машина  выдает  результат  “y”  для  входа  “x”  со  сложностью  m  (временной,  ленточной) и  вероятностью  “p”,  если  на  входе  “x”  с  вероятностью  не  меньшей  p,  израсходовав  не  более  m  единиц (шагов,  ячеек  памяти),  машина  останавливается  с  результатом  “y”. Таким  образом,  для  вероятностной  машины  возможно,  хотя  и  с  малой  долей  вероятности,  получить  неверный  результат.

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

  Две  теоремы  Фрейвальда1)  показывают,  что  переход  к  вероятностным  вычислениям  приводит  к  выигрышу  не  только  во  времени,  но  и  в  пространстве.

  Здесь  будут  рассмотрены  два  класса  языков,  определяемых  машинами  Тьюринга,  использующими  при  вычислениях  случайные  числа.  Примером  рандомизированного  алгоритма  может  служить  алгоритм  “быстрой  сортировки”:  из  списка  a1, a2,…,a n  выбирается  ведущий  элемент  a v,  после  чего  список  распадается  на  два – соответственно,  меньших  и  больших  a v  элементов.  Далее  можно  рекурсивно  отсортировать  оба  списка,  в  результате  получится  отсортированный  список  a1, a2,…,a n.  Выбор  ведущего  элемента  в  списке  случаен  с  вероятностью  1/n.  Ожидаемое  время  выполнения  быстрой  сортировки  O(n log2 n).