Формальные языки
Вероятностные автоматы и BPP
Redis хранит количество уникальных посетителей миллиарда страниц в 12 килобайт памяти с точностью 99.2%. HyperLogLog - рандомизированный алгоритм из теории вероятностных вычислений. Miller-Rabin проверяет простоту чисел для RSA каждый раз когда открывается HTTPS соединение.
- Miller-Rabin: OpenSSL использует для генерации RSA ключей, Python sympy.isprime
- HyperLogLog: Redis PFADD/PFCOUNT, Google BigQuery approx_count_distinct, ClickHouse uniqHLL12
- Bloom filter: PostgreSQL использует для ускорения index scans, Chrome для Safe Browsing
- Шварц-Зиппель: проверка тождественности полиномов в символьной математике (SymPy, Mathematica)
Вероятностные конечные автоматы
Вероятностный конечный автомат (PFA) - DFA где переходы - стохастические матрицы. На символ 'a' из состояния q автомат переходит в q' с вероятностью P(q, a, q'). Принятие: достигнуто принимающее состояние с вероятностью > lambda (порог).
PFA строго мощнее DFA: существуют языки, принимаемые PFA с порогом lambda = 1/2, которые не являются регулярными. Это удивительно: кажется что случайность не должна добавлять распознающую мощность, но порог создаёт нелинейность.
Почему PFA с изолированным порогом принятия мощнее DFA?
BPP: bounded-error probabilistic poly
BPP (Bounded-error Probabilistic Polynomial time) - задачи, решаемые рандомизированной TM за полиномиальное время с вероятностью ошибки не более 1/3. Ошибка уменьшается повторением: k запусков дают ошибку (1/3)^k.
- P ⊆ BPP ⊆ PSPACE - BPP в полиноминальной памяти
- Считается что P = BPP (но не доказано): randomness не помогает асимптотически
- Derandomization: любой BPP алгоритм можно разерандомизировать при P = BPP
- Miller-Rabin: используется в OpenSSL, GnuPG, Python cryptography
- Шварц-Зиппель: проверка тождественности полиномов за O(n) с малой ошибкой
Почему BPP-алгоритм с вероятностью ошибки 1/3 практически надёжен?
RP, co-RP и ZPP
RP (Randomized Polynomial) - односторонняя ошибка: если x ∈ L, принимает с вероятностью >= 1/2; если x ∉ L, всегда отвергает. co-RP симметрично. ZPP = RP ∩ co-RP: всегда правильный ответ, но случайное время.
Почему ZPP = RP ∩ co-RP, а не просто класс алгоритмов без ошибок?
Рандомизированные алгоритмы в практике
Рандомизация часто упрощает алгоритм и улучшает средний случай. Рандомизированный quicksort, skip list, bloom filter, HyperLogLog - всё это применение случайности для практической эффективности.
Почему HyperLogLog использует позицию первого 1-бита, а не просто случайное число?
Итоги
- PFA строго мощнее DFA с изолированным порогом за счёт вещественных амплитуд
- BPP: ошибка <= 1/3, амплифицируется повторением, предположительно равен P
- RP/co-RP/ZPP: односторонняя ошибка - более строгие подклассы BPP
- Практика: Miller-Rabin (RP), HyperLogLog (BPP), quicksort (ZPP)
Связанные темы
Вероятностные вычисления связывают теорию автоматов с алгоритмами и криптографией:
- Квантовые вычисления — BQP - квантовый аналог BPP: вместо классической монеты - квантовая суперпозиция
- Теорема PCP — PCP связывает рандомизацию с аппроксимируемостью NP-задач
- Коммуникационная сложность — Рандомизация существенно снижает коммуникационную сложность (equality testing: O(1) vs O(n))
- Криптография — Derandomization предполагает существование криптографических PRG - связь P=BPP с OWF
Вопросы для размышления
- Если P = BPP, что это означает для практики рандомизированных алгоритмов?
- Почему односторонняя ошибка (RP) часто предпочтительнее двусторонней (BPP)?
- Как derandomization через pseudorandom generators позволяет превратить BPP-алгоритм в детерминированный?