Анализ сложности в среднем. Вероятностные алгоритмы

            Используя результат следующего упражнения: покажите, что для любых двух событий E₁, E₂,

мы получаем, что вероятность  события Q(r₁,r₂,...,r_n) = 0 не превосходит суммы

двух вероятностей d − k/|S| и k/|S|, что дает в сумме желаемое d/|S|.

Упражнение 37 Имеется квадратная, n Ч n матрица A, элементами которой

являются линейные функции f_ij(x) = a_ijx + b_ij.

Придумайте Монте-Карло  алгоритм с односторонней ошибкой, для проверки

этой матрицы на вырожденность (detA ≡ 0).

              Еще одним примером успеха вероятностных алгоритмов является разработка эффективных вероятностных алгоритмов проверки простоты числа: для натурального числа n заданного в двоичной системе, определить является ли оно простым. Только в 2002 г. для этой задачи удалось построить полиномиальный детерминированный алгоритм.

             Одной из многочисленных областей, где широко применяются вероятностные алгоритмы, являются параллельные вычисления. Эффективным параллельным алгоритмом (или NC-алгоритмом) называется алгоритм, который на многопроцессорной RAM (так называемой PRAM) с числом процессоров не превосходящих некоторого полинома завершает работу за время ограниченное полиномом от логарифма длины входа. Построение эффективного детерминированного параллельного алгоритма (NC-алгоритма) для нахождения максимального паросочетания в двудольном графе является одной из основных открытых проблем в теории параллельных алгоритмов. Удалось, однако, построить эффективный параллельный вероятностный алгоритм нахождения максимального паросочетания в двудольном графе (так называемый RNC-алгоритм).

             Интересным свойством предикатов из класса BP P является наличие для них схем из функциональных элементов (boolean circuits) полиномиального размера.

             Класс всех предикатов, для которых существуют такие схемы обозначается P/poly.