BPP, RP, ZPP: рандомизированные алгоритмы

1977 год. Михаэль Рабин публикует тест простоты. Рандомизированный алгоритм проверяет 1024-битное RSA-число за 10 миллисекунд с вероятностью ошибки меньше $2^{-128}$. Детерминированный алгоритм с той же гарантией потребовал бы времени, превышающего возраст Вселенной. Каждый раз, когда браузер устанавливает HTTPS-соединение - где-то выполняется этот тест. Рандомизация - не костыль. Это отдельный вычислительный класс с собственной теорией.

• Miller-Rabin в OpenSSL и BoringSSL: генерация RSA-ключей при каждом TLS-handshake
• Randomized quicksort в C++ STL, Python, Java - ожидаемое O(n log n) без деградации на sorted input
• Monte Carlo Tree Search в AlphaGo/AlphaZero: случайные rollouts для оценки миллионов позиций
• Randomized SVD в scikit-learn: PCA на матрицах 10^6 x 10^4 за секунды вместо часов
• Bloom filter в Redis, Cassandra, Chrome Safe Browsing: вероятностная структура в духе RP

Monte Carlo vs Las Vegas: два разных компромисса

1977 год. Гэри Миллер предлагает тест простоты числа, основанный на гипотезе Римана. Михаэль Рабин убирает гипотезу и делает тест рандомизированным. Результат: проверка 1024-битного RSA-числа за 10 миллисекунд с вероятностью ошибки менее $2^{-128}$. Детерминированный алгоритм с той же гарантией потребовал бы времени, сравнимого с возрастом Вселенной. Каждый HTTPS-handshake в интернете работает на этом компромиссе.

Рандомизированные алгоритмы бросают монету в процессе работы. Это не просто оптимизация - это другая вычислительная модель. Машина Тьюринга получает дополнительную ленту со случайными битами и может читать их в любой момент. Два принципиально разных подхода к ошибке разделяют мир рандомизированных алгоритмов.

Randomized quicksort - классический Las Vegas. Выбор пивота случаен, но сортировка всегда правильная. Ожидаемое время $O(n \log n)$, наихудший случай $O(n^2)$ - но он случается с вероятностью $2^{-n}$ при случайном выборе. В стандартной библиотеке C++, Python, Java - именно этот вариант.

Monte Carlo Tree Search в AlphaGo - другой архетип. Случайные rollouts оценивают позиции: алгоритм смотрит на тысячи случайных концовок партии и усредняет. Никакой гарантии оптимальности хода, но статистика сходится. Именно этим AlphaGo в 2016 году обыграл Ли Седоля - детерминированный минимакс не справился бы с разветвлённостью дерева го.

**Усиление уверенности (amplification):** порог ошибки 1/3 в BPP - произвольная константа. Запустить алгоритм $k$ раз, взять большинство голосов - вероятность ошибки падает до $2^{-\Omega(k)}$. За 100 запусков ошибка становится $\approx 2^{-100}$. Это бесплатно по порядку роста сложности.

BPP, RP, coRP, ZPP: таксономия вероятностных классов

Четыре основных вероятностных класса выстраиваются по типу допустимой ошибки. Самый жёсткий - **ZPP** (Zero-error Probabilistic Polynomial time): алгоритм всегда правильный, ожидаемое время полиномиальное. ZPP = RP $\cap$ coRP - красивый факт, доказываемый в три строки.

**RP** (Randomized Polynomial time) допускает одностороннюю ошибку: если $x \in L$ - алгоритм говорит YES с вероятностью $\geq 1/2$; если $x \notin L$ - говорит NO гарантированно. Ложного срабатывания на NO нет.

**coRP** - симметрично: YES-входы определяются точно, NO-входы - с вероятностью $\geq 1/2$. Тест Миллера-Рабина лежит в coRP: простые числа он называет простыми гарантированно, составные - с вероятностью $\geq 3/4$. **BPP** - самый мягкий: двусторонняя ошибка $\leq 1/3$ на любом входе.

**ZPP = RP ∩ coRP:** если есть RP-алгоритм для L и coRP-алгоритм для дополнения L, запускать их поочерёдно. Когда один даёт точный ответ - остановиться. Ожидаемое время полиномиальное, ошибок нет. Это и есть ZPP.

Включение RP $\subseteq$ NP - прямое: недетерминированная машина угадывает случайные биты, которые привели к YES. Обратное неизвестно. P $\subseteq$ ZPP $\subseteq$ RP $\subseteq$ BPP - цепочка включений, ни одно из которых не доказано строгим. Это центральный открытый вопрос дерандомизации.

Дерандомизация: можно ли убрать монетку?

Центральная гипотеза: **BPP = P**. Если это правда, случайность ничего не даёт - любой рандомизированный алгоритм можно симулировать детерминированным за полиномиальное время. Если неправда - существуют задачи, где монетка принципиально ускоряет вычисление. Ответа нет ни в ту, ни в другую сторону.

Теорема Адлемана (1978): BPP $\subseteq$ P/poly. Для каждой длины входа $n$ существует 'подсказка' (advice) полиномиального размера, с которой задача решается детерминированно. Проблема: advice зависит от $n$ и не вычислима эффективно. P/poly содержит неразрешимые задачи - это не полиномиальное время в обычном смысле.

**Псевдослучайные генераторы (PRG)** - главный инструмент дерандомизации. PRG растягивает короткое зерно (seed) длины $O(\log n)$ в строку длины $n$, неотличимую от истинно случайной для любого алгоритма ограниченного размера. Перебрать все $2^{O(\log n)} = \text{poly}(n)$ зёрен детерминированно - полиномиальное время.

Теорема Импальяццо-Вигдерсона (1997): если существуют функции, вычислимые за $2^{O(n)}$ времени, но требующие схем размера $2^{\Omega(n)}$ - тогда BPP = P. Иначе: если 'сложные' функции существуют, из них строится PRG и дерандомизация работает. Это переводит BPP = P в вопрос о circuit lower bounds - такой же открытый.

В ML рандомизация повсюду - и её тоже дерандомизируют. Dropout во время инференса заменяется масштабированием весов (детерминированная аппроксимация Monte Carlo оценки матожидания). Randomized SVD в scikit-learn использует PRG с фиксированным seed для воспроизводимости. Mini-batch SGD рандомизирован, но порядок батчей фиксируют через `torch.manual_seed` - частичная дерандомизация ради воспроизводимости экспериментов.

Алгоритм AKS (Агравал-Каял-Саксена, 2002) - историческая точка: PRIMES $\in$ P. Первый детерминированный полиномиальный тест простоты. Он дерандомизировал Миллера-Рабина. На практике AKS медленнее рандомизированного варианта - полиномиальность не гарантирует быстроты. Miller-Rabin с 128 итерациями остаётся стандартом в OpenSSL, BoringSSL, LibreSSL.

**Криптографический контрапункт:** если BPP = P и PRG существуют - это предполагает существование односторонних функций, на которых держится криптография с открытым ключом. Теория сложности и криптография переплетены глубже, чем кажется: открытый вопрос о BPP - это одновременно вопрос о безопасности RSA.

Связанные темы

Вероятностные классы сложности стыкуются с теорией вероятностей, криптографией и автоматами

• P vs NP — BPP и RP - промежуточные классы между P и NP; дерандомизационная гипотеза BPP=P
• Теорема Байеса — Amplification вероятности ошибки - тот же итеративный байес-апдейт
• Circuit Complexity — BPP ⊆ P/poly - связь с нерандомизированными схемами полиномиального размера
• Криптография — PRG <-> односторонние функции: BPP=P эквивалентно существованию OWF

Итоги

• BPP - задачи с двусторонней ошибкой <= 1/3; amplification снижает ошибку до 2^{-k} за k запусков
• RP - односторонняя ошибка (только на YES-входах); coRP - симметрично; ZPP = RP ∩ coRP (Las Vegas)
• P ⊆ ZPP ⊆ RP ⊆ BPP; RP ⊆ NP; ни одно включение не доказано строгим
• Дерандомизационная гипотеза BPP=P - эквивалентна PRG из функций с экспоненциальной схемной сложностью
• AKS 2002: PRIMES ∈ P - дерандомизация Миллера-Рабина; на практике медленнее рандомизированного варианта

Вопросы для размышления

• Если BPP = P доказано - что это означает для криптографии с открытым ключом? Должны ли существовать односторонние функции в этом мире, и где тогда проходит граница между 'случайным' и 'псевдослучайным' с точки зрения вычислений?

Связанные уроки

• cplx-05 — L/NL как фундамент понимания вычислительных ресурсов
• cplx-01 — P и NP - базовые классы, от которых отталкиваются BPP и RP
• prob-04-bayes — Байес-апдейт - снижение неопределённости через итерации
• alg-01-big-o — Вероятностный анализ строится поверх O-нотации
• fl-05-regex — Недетерминизм в автоматах - структурный аналог рандомизации