106
правок
Изменения
→Увеличение вероятности успеха в алгоритмах с датчиком случайных чисел
С помощью расширяющего графа можно посторить линейный код, позволяющий исправлять ошибки в доле <tex>\delta = 1/(2000d)</tex> битов. Чтобы задать линейный код с длиной кодового слова n, достаточно описать его проверочную матрицу <tex>H</tex> <tex>(</tex>слово <tex>x \in \{0, 1\}^n</tex> является кодовым словом если и только если <tex>Hx^t = 0)</tex>. Другими словами, нужно задать систему линейных уравнений для переменных <tex>x_1, . . . , x_n;</tex> решения этой системы и будут кодовыми словами.
===Увеличение вероятности успеха в алгоритмах с датчиком случайных чисел===
{{Определение
|definition=Язык <tex>L</tex> принадлежит сложностному классу <tex>RP</tex>, если существует полиномиальный алгоритм <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 > 1/\epsilon</tex>. Новый алгоритм действует следующим образом: выбирается случайная вершина <tex>v</tex> из левой доли графа (для этого требуется <tex>k</tex> случайных битов); затем исходный алгоритм <tex>A</tex> последовательно запускается на всех <tex>d</tex> наборах случайных битов, соответствующих соседям вершины <tex>v</tex>. Если все полученные ответы равны <tex>1</tex>, новый алгоритм также возвращает единицу; в противном случае возвращается ноль.
Покажем, что у нового алгоритма вероятность ошибки не превосходит <tex>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> состоит из вершин, все соседи которых лежат в B. Предположим, что <tex>S</tex> содержит не менее <tex>n/(1000d)</tex> вершин. Выберем среди них ровно <tex>n/(1000d)</tex> вершин и назовём это множество <tex>S'</tex>. По свойству экспандера, имеем
<tex>|\Gamma(S')| \geqslant \frac{7}{8}d\frac{n}{1000d}=7n/8000 > n/2000</tex>
Это противоречит тому, что все соседи <tex>S'</tex> лежат в <tex>B</tex>. В данном случае нам нужна явная в более сильном (чем в первом примере) смысле конструкция экспандера. Размер графа экспоненциално растёт с увеличенем <tex>k</tex>, и нам необходим алгоритм, который по заданному номеру вершины <tex>v</tex> (из левой доли графа) за время <tex>poly(k)</tex> находит список номеров всех соседей этой вершины (в правой доле графа).
===Хранение множества со сверхбыстрым запросом элементов===
