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

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

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

Задача

Есть полином с целыми коэффициентами. Нужно проверить, является ли полином тождественным нулем. Будем считать что полином представлен в виде арифметической схемы. Арифметическая схема похожа на логическую только вместо операций [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].