Участник: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]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] схемы, а это значит что он может быть эффективно реализован используя параллельные вычисления.