92
правки
Изменения
м
{{Определение
|definition=Язык <tex>L</tex> принадлежит сложностному [[RP|классу ''RP'']], если существует полиномиальный алгоритм <tex>A</tex> такой что
1. для <tex>x \in L</tex> для всех <tex>r \in \{0, 1\}^{poly(n)}</tex> <tex>A(x, r) = 1</tex>
2. для <tex>x \notin L</tex> не более чем для 1/2000 всех <tex>r \in \{0, 1\}^{poly(n)}</tex> может выполняться <tex>A(x, r) = 1</tex>
}}
→Увеличение вероятности успеха в алгоритмах с датчиком случайных чисел
===Увеличение вероятности успеха в алгоритмах с датчиком случайных чисел===
Покажем, что для любого <tex>\epsilon > 0</tex> полиномиальный вероятностный алгоритм A можно модифицировать таким образом, чтобы вероятность ошибки уменьшилась до <tex>\epsilon</tex>, а число используемых случайных битов не изменится.
Пусть исходный алгоритм использует <tex>k = k(n)</tex> случайных битов для вычислений на входах длины <tex>n</tex>. Зафиксируем <tex>(2^k, 2^k, d)</tex> - экспандер <tex>G</tex>, где <tex>d > \cfrac{1/}{\epsilon}</tex>. Новый алгоритм действует следующим образом: выбирается случайная вершина <tex>v</tex> из левой доли графа (для этого требуется <tex>k</tex> случайных битов); затем исходный алгоритм <tex>A</tex> последовательно запускается на всех <tex>d</tex> наборах случайных битов, соответствующих соседям вершины <tex>v</tex>. Если все полученные ответы равны <tex>1</tex>, новый алгоритм также возвращает единицу; в противном случае возвращается ноль.Покажем, что у нового алгоритма вероятность ошибки не превосходит <tex>\cfrac{1/}{d}</tex>. В самом деле, обозначим <tex>B = B(x)</tex> множество таких вершин <tex>w</tex> из правой доли графа, которые соответствуют неверному ответу старого алгоритма на входе <tex>x</tex>; аналогично, обозначим <tex>S = S(x)</tex> множество таких вершин v из левой доли графа, которые для которых новый алгоритм даёт неверный ответ на входе <tex>x</tex>. Очевидно, <tex>S</tex> состоит из вершин, все соседи которых лежат в <tex>B</tex>. Предположим, что <tex>S</tex> содержит не менее <tex>\cfrac{n/(}{1000d)}</tex> вершин. Выберем среди них ровно <tex>\cfrac{n/(}{1000d)}</tex> вершин и назовём это множество <tex>S'</tex>. По свойству экспандера, имеем
<tex>|\Gamma(S')| \geqslant \cfrac{77nd}{8\cdot 1000d}d= \cfrac{n7n}{1000d8000}=7n/8000 > \cfrac{n/}{2000}</tex>
Это противоречит тому, что все соседи <tex>S'</tex> лежат в <tex>B</tex>. В данном случае нам нужна явная в более сильном (чем в первом примере) смысле конструкция экспандера. Размер графа экспоненциално растёт с увеличенем <tex>k</tex>, и нам необходим алгоритм, который по заданному номеру вершины <tex>v</tex> (из левой доли графа) за время <tex>poly(k)</tex> находит список номеров всех соседей этой вершины (в правой доле графа).
