Участник:Zerogerc

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

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

Задача

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

Алгоритм

Нам нужен детерминированный алгоритм работающий за [math]p(\log|n|)[/math], где [math]p[/math] — полином. Однако не существует такого эффективного алгоритма. Однако существует эффективный рандомизированный алгоритм. Формально, нам нужно проверить принадлежит ли число языку [math]PRIMES = \{ \llcorner N \lrcorner : N -[/math] простое [math]\}[/math]. Для каждого [math]N[/math] и [math]A \in [N - 1][/math], определим:

[math] QR_N(A) = \begin{cases} 0 & gcd(A, N) \ne 1\\ +1 & A = B^2 (mod N), gcd(B, N) = 1\\ - 1, & \text{otherwise} \end{cases} [/math]

— Для каждого нечетного простого [math]N[/math] и [math]A \in [N - 1], QR_N(A) = A^{(N - 1)/2} (mod N)[/math]

— Для каждого нечетного [math]N, A[/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]. Заметим что сивол Якоби вычислим за [math]O(logA * logN)[/math]

— Для каждого нечетного составного [math]N, |\{A \in [N - 1]: gcd(N, A) = 1 \,and\,(\frac{N}{A}) = A^{\frac{N - 1}{2}}\}| \le \frac{1}{2}[/math] [math]\,| \{A \in [N - 1]: gcd(N, A) = 1\}|[/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]let 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] схемы, а это значит что он может быть эффективно реализован используя параллельные вычисления.