Изменения

Нам нужен детерминированный Существует эффективный рандомизированный алгоритм работающий за <tex>p(\log|n|)</tex>, где <tex>p</tex> {{---}} полином. Хоть и В то время как не существует такого эффективного детерминированного алгоритма, существует эффективный рандомизированный алгоритмс такой же ассимптотикой.

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

0 & gcdA \equiv 0 \ (A, mod\ N) \ne 1\\ +1 & A = B^2 \not\equiv 0 \ (mod \ N), gcd\ \exists x: A \equiv x^2 \ (B, mod \ N) = 1\\

{{---}} Для каждого нечетного простого <tex>N</tex> и <tex>A \in [1 0\,.. \,N - 1], QR_N</tex> определим симол Якоби <tex>(\frac{N}{A}) </tex> как <tex>\prod\limits_{i= A1}^k QR_{P(i)}(A)</tex>, где <tex>P_1, ... , P_k</tex> это простые делители (не обязательно различные) числа <tex>N (N - = \prod\limits_{i=1}^k P_i)</2} tex>. Cуществует алгоритм для вычисления символа Якоби за <tex>O(mod NlogA \cdot logN)</tex>. Можно посмотреть на [https://en.wikipedia.org/wiki/Jacobi_symbol википедии] 

{{---}} Для каждого нечетного простого <tex>N, A</tex> определим симол Якоби и <tex>(\frac{N}{A})</tex> как <tex>\prod\limits_{i=in [1}^k QR_{P(i)}(A)</tex>, где <tex>P_1, ... , P_kN - 1]</tex> это простые делители (не обязательно различные) числа выполняется: <tex>N QR_N(N A) = A^{\prod\limits_frac{i=N - 1}^k P_i)</tex>. Заметим что сивол Якоби вычислим за <tex>O{2}} (logA * logNmod \ N)</tex>{{---}} формула Лежандра

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

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

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

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

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

Если <tex>C \in ZEROP</tex>, то алгорим алгоритм всегда выдаст правильный ответ. Если <tex>C \notin ZEROP</tex> то алгоритм выдаст правильный ответ с вероятностью <tex>\ge \frac{9}{10}</tex>. Однако есть проблема. Числа которые получаются в результате вычисленний могут быть порядка <tex>(10 \cdot 2^m)^{2^m}</tex>. Такие числа требуют экспоненциальное число бит только для представления не говоря уже про операции над ними. Мы решим эту проблему с помощью вычислений по модулю <tex>k</tex>, где <tex>k</tex> - слуйчайное число <tex>\le 2^{2^m}</tex>. Таким образом вместо вычисления <tex>y = C(x_1, x_2, ..., x_m)</tex>, мы считаем значение <tex>y \ (mod \ k)</tex>. Очевидно что если <tex>y = 0</tex>, то <tex>y \ mod \ k = 0</tex>. Утверждается что если <tex>y \ne 0</tex>, то с вероятностью хотя бы <tex>\delta = \frac{1}{10m}</tex>, <tex>k</tex> не делится на <tex>y</tex>. Действительно, пусть <tex>y \ne 0</tex> и пусть <tex>S = {p_1, ..., p_l}</tex> {{---}} множество простых делителей <tex>y</tex>. Достаточно показать что с вероятностью <tex>\ge \delta</tex>, <tex>k</tex> будет простым числов <tex>\notin S</tex>. По теореме о простых числах верятность того что <tex>k</tex> будет простым числом <tex>\ge \frac{1}{5m} = 2 \delta</tex>. А так как <tex>y</tex> может иметь максимум <tex>log(y) \le 5m2^m</tex> различных простых делителей, вероятность того что <tex>k \in S \le \frac{5m2^m}{2^{2^m}} << \frac{1}{[10m]} = \delta</tex>. Объединяя эти факты получаем что с вероятнотью хотя бы <tex>\delta</tex>, <tex>y</tex> не будет делиться на <tex>k</tex>. == См. также ==<references/>* [[Вероятностные вычисления. Вероятностная машина Тьюринга]]*[[Лемма Шварца-Зиппеля]] == Литература ==* [http://www.cs.princeton.edu/theory/complexity/ Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach] == Ссылки ==* [https://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D0%BC%D0%B2%D0%BE%D0%BB_%D0%AF%D0%BA%D0%BE%D0%B1%D0%B8 Символ Якоби]* [https://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D0%BC%D0%B2%D0%BE%D0%BB_%D0%9B%D0%B5%D0%B6%D0%B0%D0%BD%D0%B4%D1%80%D0%B0 Символ Лежандра]* [https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE_%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B8_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%8B%D1%85_%D1%87%D0%B8%D1%81%D0%B5%D0%BB Теорема о распределении простых чисел]* [https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D1%81%D1%82_%D0%A1%D0%BE%D0%BB%D0%BE%D0%B2%D0%B5%D1%8F_%E2%80%94_%D0%A8%D1%82%D1%80%D0%B0%D1%81%D1%81%D0%B5%D0%BD%D0%B0 Тест Соловея — Штрассена]

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