Участник:Zerogerc

Примеры рандомизированных алгоритмов

Проверка числа на простоту

Задача

Дано целое число [math]N[/math]. Определить является ли оно простым.

Алгоритм

Нам нужен детерминированный алгоритм работающий за [math]p(\log|n|)[/math], где [math]p[/math] — полином. Хоть и не существует такого эффективного детерминированного алгоритма, существует эффективный рандомизированный алгоритм.

Формально, нам нужно проверить принадлежит ли число языку [math]PRIMES = \{ \llcorner N \lrcorner : N -[/math] простое [math]\}[/math]. Предоставим алгоритм который покажет что [math]PRIMES \in BPP[/math]. Для каждого [math]N[/math] и [math]A \in [1 .. N - 1][/math], определим символ Лежандра:

[math] QR_N(A) = \begin{cases} 0 & A \equiv 0 \ (mod\ N) \\ +1 & A \not\equiv 0 \ ( mod \ N), \ \exists x: A \equiv x^2 \ (mod \ N) = 1\\ - 1, & \text{otherwise} \end{cases} [/math]

Для каждого нечетного [math]N[/math] и [math]A \in [0\,..\,N-1][/math] определим симол Якоби [math](\frac{N}{A})[/math] как [math]\prod\limits_{i=1}^k QR_{P(i)}(A)[/math], где [math]P_1, ... , P_k[/math] это простые делители (не обязательно различные) числа [math]N (N = \prod\limits_{i=1}^k P_i)[/math]. Cуществует алгоритм для вычисления символа Якоби за [math]O(logA \cdot logN)[/math]. Можно посмотреть на википедии

— Для каждого нечетного простого [math]N[/math] и [math]A \in [1 .. N - 1][/math] выполняется: [math]QR_N(A) = A^{\frac{N - 1}{2}} (mod \ N)[/math] — формула Лежандра

— Также доказано что для каждого нечетного составного [math]N, |\{A \in [1\,..\,N - 1]: gcd(N, A) = 1[/math] и [math](\frac{N}{A}) = A^{\frac{N - 1}{2}}\}| \le \frac{N}{2}[/math]

Собирая эти факты вместе, получаем просто алгоритм. Для данного [math]N[/math] выбираем случайное число [math]A: 1 \le A \lt N[/math], если [math]gcd(N,A) \gt 1[/math] или [math](\frac{N}{A}) \ne A^{\frac{N - 1}{2}} (mod \, N)[/math] тогда говорим что число составное, иначе говорим что оно простое. Этот алгоритм всегда скажет что число простое, если оно действительно простое. Однако если число составное, то алгоритм скажет что оно составное с вероятностью [math] \ge \frac{1}{2}[/math].

Заметим что повторяя этот алгоритм несколько раз можно увеличить вероятность правильного ответа.

Проверка двудольного графа на существование в нем полного паросочетания

Задача

Пусть [math]G = (V_1, V_2, E)[/math] — двудольный граф, где [math]|V_1|=|V_2|[/math] и [math]E \subseteq V_1 \times V_2[/math], тогда полным паросочетанием называется [math]E' \subseteq E[/math] такое что каждая вершина является концом ровно одного ребра из [math]E'[/math]. Нужно проверить, существует ли в графе полное паросочетание.

Алгоритм

Пусть у нас есть матрица [math]X[/math] размером [math]n \times n[/math], где [math]n = |V_1| = |V_2|[/math]. Пусть [math]X_{ij} = x_{ij}[/math] если [math](i,j) \in E[/math], [math]0[/math] иначе. Пусть детерминант матрицы [math]det(X) = \sum\nolimits_{\sigma \in S_n} (-1)^{sign(\sigma)} \prod\limits_{i=1}^n X_{i,\sigma(i)}[/math]. Где [math]S_n[/math] это множество всех перестановок [math]{1, 2, ..., n}[/math]. Каждая такая перестановка это возможное полное паросочетание. Тогда ясно что [math]det(X) \ne 0 \iff[/math] когда в [math]G \: \exists[/math] полное паросочетание. Таким образом: в графе [math]\exists[/math] полное паросочетание [math]\iff det(X) \ne 0[/math]

Заметим две вещи. Первое: у полинома [math]det(X)[/math] всего [math]|E|[/math] переменных и общая степень не более [math]n[/math]. Второе: хотя размер [math]det(X)[/math] может быть экспоненциальным, для точно заданных значений [math]x_{ij}[/math] cуществуют известные полиномиальные алгоритмы. (задача вычисления детерминанта [math]\in NC^2[/math])

Это ведет нас к алоритму, который называется рандомизированный алгоритм Ловаса. Сформулируем его: выберем случайные числа для [math]x_{ij}[/math]. Если [math]det(X) \ne 0[/math] значит говорим что в графе есть полное паросочетание, иначе говорим что нету. Основное преимущество этого алгоритма в том, что он может быть реализован с помощью рандомизированной [math]NC[/math] схемы, а это значит что он может быть эффективно реализован используя параллельные вычисления.

Проверка полиномов на равенство

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

Задача

Есть полином с целыми коэффициентами. Нужно проверить, является ли полином тождественным нулем. Будем считать что полином представлен в виде арифметической схемы. Арифметическая схема похожа на логическую только вместо операций [math]{\land, \lor, \neg}[/math] она использует операции [math]{+, -, \times}[/math]. Формально это ориентированный граф в котором есть [math]n[/math] источников и каждая вершина не являющаяся источником имеет два входа и один выход. Есть одна вершина являющаяся стоком. Каждая внутренняя вершина помечена одной из трех aрифметических операций. Значение полинома считается путем помещения на источники целых чисел и применения всех операций в порядке заданном графом.

Заметим что исходная задача звучала как проверка двух полиномов не равенство. Мы сведем ее к проверке полинома на равенство нулю путем такого преобразования: пусть у нас было две арифметические схемы [math]C, C'[/math] которые нужно проверить на равенство. Мы строим новую схему [math]D : D(x_1, ..., x_n) = C(x_1, ..., x_n) - C'(x_1, ..., x_n)[/math]. Определим класс [math]ZEROP[/math] как класс всех схем которые обращаются в ноль на всех возможных входах. Тогда задача будет звучать как проверить принадлежит ли [math]D[/math] классу [math]ZEROP[/math]

Алгоритм

Так как раскрытие всех скобок в полиноме может привести к экспоненциальному количеству мономов. То проверка на принадлежность классу [math]ZEROP[/math] может оказаться довольно затратной по времени. Однако существует эффективный рандомизированный алгоритм основанный на лемме Шварца-Зиппеля, которую здесь мы оставим без доказательства.

Лемма:

Пусть [math]p(x_1, x_2, ..., x_m)[/math] полином с общей степенью не более [math]d[/math]. [math]S[/math] — конечный набор чисел. Тогда если [math]a_1, a_2, ..., a_m[/math] случайно выбранные числа из [math]S[/math] то: [math]Pr[p(a_1, a_2, ..., a_m) \ne 0] \ge 1 - \frac{d}{|S|}[/math]. Где [math]Pr[x][/math] — вероятность события [math]x[/math]

Нетрудно видеть что у схемы [math]C[/math] размера [math]m[/math] с [math]n[/math] переменными общая степень не больше [math]2^m[/math]. Получаем следующий алгоритм: выбираем [math]n[/math] чисел из набора [math][1 .. 10 \cdot 2^m][/math]. Вычисляем схему на этих числах. Если получился ноль то говорим что [math]C \in ZEROP[/math]. Иначе говорим что [math]C \notin ZEROP[/math].

Если [math]C \in ZEROP[/math], то алгоритм всегда выдаст правильный ответ. Если [math]C \notin ZEROP[/math] то алгоритм выдаст правильный ответ с вероятностью [math]\ge \frac{9}{10}[/math]. Однако есть проблема. Числа которые получаются в результате вычисленний могут быть порядка [math](10 \cdot 2^m)^{2^m}[/math]. Такие числа требуют экспоненциальное число бит только для представления не говоря уже про операции над ними.

Мы решим эту проблему с помощью вычислений по модулю [math]k[/math], где [math]k[/math] - слуйчайное число [math]\le 2^{2^m}[/math]. Таким образом вместо вычисления [math]y = C(x_1, x_2, ..., x_m)[/math], мы считаем значение [math]y \ (mod \ k)[/math]. Очевидно что если [math]y = 0[/math], то [math]y \ mod \ k = 0[/math]. Утверждается что если [math]y \ne 0[/math], то с вероятностью хотя бы [math]\delta = \frac{1}{10m}[/math], [math]k[/math] не делится на [math]y[/math]. Действительно, пусть [math]y \ne 0[/math] и пусть [math]S = {p_1, ..., p_l}[/math] — множество простых делителей [math]y[/math]. Достаточно показать что с вероятностью [math]\ge \delta[/math], [math]k[/math] будет простым числов [math]\notin S[/math]. По теореме о простых числах верятность того что [math]k[/math] будет простым числом [math]\ge \frac{1}{5m} = 2 \delta[/math]. А так как [math]y[/math] может иметь максимум [math]log(y) \le 5m2^m[/math] различных простых делителей, вероятность того что [math]k \in S \le \frac{5m2^m}{2^{2^m}} \lt \lt \frac{1}{[10m]} = \delta[/math]. Объединяя эти факты получаем что с вероятнотью хотя бы [math]\delta[/math], [math]y[/math] не будет делиться на [math]k[/math].

См. также

• Вероятностные вычисления. Вероятностная машина Тьюринга
• Лемма Шварца-Зиппеля

Литература

• Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach

Ссылки

• Символ Якоби
• Символ Лежандра
• Теорема о распределении простых чисел
• Тест Соловея — Штрассена