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

  Время  работы  МТ.  Запись  n  и  m  не  длиннее  входа,  k  выбираем  не  больше  квадрата  длины (пропорционально  n⋅m).  В  каждом  эксперименте  вход  просматривается  не  более  4-х  раз (чтобы  выбрать  ребро,  а  затем  проверить  наличие  еще  двух ребер),  поэтому  время  эксперимента  линейно  относительно  длины  входа.  Таким  образом,  до  останова  МТ совершает  не  более,  чем  ⎜w⎮3  переходов,  т. е. время  работы  МТ  полиномиально, т. е.  условие 3  выполняется.

  Все  три  условия  для  языка  L  “графов  с  треугольниками”  выполнены, так  что  L  принадлежит  классу  RP.  Также  L  принадлежит  классу  P.

Однако  найти  язык  из  класса  RP \ P  значительно  труднее.

  Для  распознавания  языка  L  из  RP  существует  рандомизированная  машина  Тьюринга  типа  Монте-Карло,  полиномиальная  по  времени.  Если  вход  w ∉ L,  машина  не  допускает,  а  в  случае  w ∈ L  также  может  произойти  ложный  негативный  исход.  Так  что  для  подтверждения  допускания  опыт  надо  провести  несколько  раз.  Справедлива  следующая  теорема.

Теорема.  Если  L  принадлежит  RP,  то  для  любой  как  угодно  малой  константы  c > 0  существует  полиномиальный  по  времени  рандомизированный  алгоритм,  совершаю - щий  ложный  негативный  исход  на  входе w ∈ L  с  вероятностью  не  больше  c.

Доказательство. Для  языка  из  L  из  RP  допускающая  его  МТ  допускает 

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

проверку  log2 (1/c)  раз.  Поскольку  время  работы  рандимизированной  МТ  полиномиально,  повторение  проверки  не  нарушит  полиномиальности.

Класс  ZPP

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

Машины  называют  МТ  типа  Лас-Вегас.  На  входах,  принадлежащих  языку  L=L(M), 

машина  останавливается,  допуская,  в  противном  случае  останавливается  без  допускания. 

  Легко доказать,  что  ZPP=co-ZPP.  Достаточно  переделать  машину  типа  Лаг-Вегас,  допускающую  язык  L  в  машину,  допускающую  язык  L’ .  Замкнутость  класса  RP  относительно  дополнения  не  очевидна,  так  как  машины  типа  Монте-Карло  трактуют  допускание  и  отвергание  несимметрично.  Однако  следующие  отношения  имеют  место.

Теорема.  ZPP = RP = co-RP.

Доказательство.  1)  RP ∩ co-RP ⊆ ZPP :  Пусть  L∈ RP ∩ co-RP,  т. е. L  и  L’

допускаются  МТ  типа  Монте-Карло  с  полиномиально  ограниченным  временем.  Возьмем  полином,  ограничивающий  время  работы  обеих  машин.  Построим  для  L  МТ  M  типа  Лас-Вегас:

Сначала  работает  машина  для  L  типа  Монте-Карло,  если  она  допус

кает,  M  допускает  и  останавливается.

Если  машина  для  L  не  допускает  (останавливается,  не  допуская),  за -

пустим  машину  типа  Монте-Карло  для  L’.  Если  эта  МТ  допускает,  M  останавливается,  не  допуская. В  противном  случае  возвращаемся  к  п.1. 

  M  допускает,  если  вход  w ∈ L;  M  отвергает  w,  если  w ∉ L. Ожидаемое  время  в  одном  цикле – 2p(n).  Вероятность  того,  что  один  цикл  разрешит  вопрос  не  меньше  Ѕ.  Если  w ∈ L,  то  п.1  имеет  вероятность  Ѕ  привести  машину  M  к  допусканию,  а если  w ∉ L – столько  же  шансов  привести  M  к  отверганию.  Таким  образом,  ожидаемое  время  работы  машины  M  не  больше 2p(n) + (1/2)2p(n) + (1/4)2p(n) + (1/8)p(n) +…= 4p(n).

2) ZPP ⊆ RP ∩ co-RP : Пусть  L ∈ ZPP,  тогда  язык  L  допускается  МТ  M1 типа  Лас-Вегас,  ожидаемое  время  работы  которой  - некоторый  полином  p(n).  Построим  для  L  МТ  M2  типа  Монте-Карло:  M2  имитирует  2p(n)  шагов  работы  M1.  Если  M1  допускает в  течение  этого  времени,  M2  также  допускает,  в  противном  случае  она  отвергает. 

  Если  вход  w ∉ L,  то  M1  не  допускает,  если w ∈ L,  то  M1  допустит,  но  время  ее  работы  может  превысить  2p(n).  Гарантия,  что  это  произойдет  в  пределах  2p(n)  не  меньше  Ѕ.  Допустим  противное:  время  работы  не  больше  2p(n)  с  вероятностью  c < Ѕ.  Тогда  ожидаемое  время  работы  M1  на  входе  w  не  меньше  (1 - c)2p(n),  поскольку  1 – c  является  вероятностью  того,  что  M1  надо  времени  больше,  чем  2p(n).  Но  2(1 - c) > 1,  так  что  ожидаемое  время  работы  M1  больше  p(n).  Тогда  и  время  допускания  машины  M2  не  меньше  Ѕ.  Таким  образом  построенная  машина  M2  типа  Монте-Карло  с  ограниченным  временем,  что  доказывает  принадлежность  L  классу  RP.

  Для  доказательства  того,  что  L ∈ co-RP  -  по  M1  строим  МТ  типа  Монте-Карло  с  полиномиально  ограниченным  временем  для  L’.

  Из  теоремы 11.17  следует,  что  ZPP ⊆  RP.  Место  этих  классов  между  P  и  NP  определяют  следующие  теоремы.

Теорема.  P ⊆  ZPP.

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

Теорема.  RP ⊆  NP.

Доказательство.  Пусть  язык  L  принадлежит  RP.  Тогда  допускающая  L  МТ  M1  типа  Монте-Карло.  Можно  построить  НМТ  M2,  моделирующую  работу  М1  и,  когда  М1  рассматривает  случайный  бит  M2  оба  возможных  значения  этого  бита  записывает  их  на  свою  случайную  ленту.

M2  допускает,  когда  M1  допускает,  и  не  допускает  в  противном  случае. 

  Возьмем  w ∈  L.  Поскольку  M1  имеет  вероятность  допускания  больше  Ѕ,  должна  существовать  последовательность  битов  на  ее  случайной  ленте,  приводящая  к  допусканию  w.  M2  берет  эту  последовательность (угадывает)  битов  и  также  допускает.  Таким  образом,  w ∈  L (M2).  Если

w ∉  L,  то  ни  одна  последовательность  случайных  битов  не  приводит  M1  к  допусканию,  следовательно,  нет  и  последовательности  случайных  битов,  приводящей  к  допусканию  M2.  Таким  образом,  w ∉  L(M2).

  На  рисунке представлены  соотношения  между  введенными  классами.

Тема 5.  Сложность  арифметических  проблем.

§ 1.  Сложность  проверки  простоты  числа.