BPP, RP и ZPP: у ошибки есть направление

Если знаешь, какой ответ твоего алгоритма достоверен - переходи к «Теперь сам».

Как думаешь: ответ «нет» тоже надёжен?

Поиск случайно перебирает кандидатов, проверяет каждого и останавливается, найдя решение. Если кандидат подходит, проверка служит сертификатом. Если за сто попыток никто не найден, решения могло не быть, а могло просто не повезти. У такого метода стороны ответа неравноправны.

Теперь другая программа с вероятностью 0,9 отвечает верно, но умеет ошибаться в обе стороны. Успешное большинство запусков снижает вероятность ошибки, однако ни один конкретный ответ сам по себе не становится доказательством. Эти два интерфейса нельзя бездумно подставлять друг вместо друга внутри большой проверки.

На что это похоже

Представь сигнализацию, которую проверяют по разным обязательствам. Одна никогда не подаёт ложную тревогу, но может пропустить событие. Другая никогда не пропускает событие, но иногда звонит зря. Третья допускает оба вида ошибки. Слово «точность 90%» стирает различие. В классе сложности вероятность ошибки ограничивается отдельно для каждого фиксированного входа, а не в среднем по удобному набору тестов.

Механизм: кванторы и повторение

Машина BPP за полиномиальное время использует полиномиальное число случайных битов. При входе из языка она принимает с вероятностью не меньше 2/3, при входе вне языка - не больше 1/3. Эти числа можно заменить другими константами, отделёнными от половины: независимое повторение и большинство уменьшают ошибку экспоненциально по числу повторов.

Для RP отрицательный вход отвергается всегда. Положительный может случайно отвергнуться, но с вероятностью не больше 1/2. Чтобы усилить RP, достаточно принять, если хотя бы один запуск принял: ошибочное принятие не появляется, а вероятность пропуска падает до 2⁻ʳ. Для coRP, наоборот, достоверен отрицательный ответ и надо отвергать, если хотя бы один запуск отверг.

ZPP - программа без ошибочных ответов, но со случайной длительностью. На каждом входе её ожидаемое время ограничено полиномом. Это не обещает полиномиальную длительность каждого запуска. Из программ RP и coRP для одного языка можно получить ZPP: чередуем независимые запуски, ждём сертификат «да» от RP или достоверное «нет» от coRP. Для правильной стороны вероятность успеха за раунд хотя бы половина, поэтому ожидается не больше двух раундов. Неверная сторона достоверного ответа не выдаст. В обратную сторону пусть ожидаемое время ZPP не превосходит полинома p(n). Останавливаем запуск через 2p(n) шагов. По неравенству Маркова вероятность таймаута не больше 1/2. Ответ «нет» при таймауте даёт RP, а ответ «да» при таймауте даёт coRP; завершившийся запуск всегда прав.

Проверка тождества многочленов показывает coRP при следующем условии на вход: известна граница общей степени разности d, а поле содержит q > 2d элементов. Даны два многочлена; спрашивается, нулевая ли их разность как формальный многочлен, а не только совпадают ли значения на данном поле. Берём разность P. Если это нулевой многочлен, любая подстановка даст ноль. Если он ненулевой общей степени не больше d, случайная независимая подстановка каждой переменной обращает его в ноль с вероятностью не больше d/q. Это лемма Шварца-Зиппеля. Общая степень - наибольшая сумма показателей в одном одночлене. При q > 2d вероятность ложного объявления тождества меньше половины. Подстановка с ненулевым значением достоверно опровергает тождество.

Условие о размере поля нужно: над полем из q элементов ненулевой формальный многочлен x^q − x равен нулю при всех подстановках. Если q ≤ 2d, описанный здесь однократный тест не обеспечивает вероятность ошибки меньше половины. Для общего случая используют, например, вычисления в подходящем расширении поля; его построение здесь не реализовано. Нельзя выдавать показанный тест за решение без условия на вход. Это также пример различия формального тождества и совпадения функций на конечном множестве.

Правило

Сначала назови сторону возможной ошибки, затем способ усиления. Независимые повторения RP объединяются по OR, coRP по AND, BPP по большинству. ZPP меняет ограничение времени на ожидаемое, сохраняя верность каждого выданного ответа.

Разбор: считаем вероятность без случайного эксперимента

Программа точно суммирует биномиальные вероятности через рациональные дроби. Это проверка математической гарантии: выборка из миллиона запусков не доказала бы верхнюю границу для всех входов.

from fractions import Fraction
from math import comb


def oshibka_bolshinstva(r, p):
    return sum((Fraction(comb(r, k)) * p ** k *
                (1 - p) ** (r - k)
                for k in range(r // 2 + 1, r + 1)),
               Fraction(0))


def P(x, y, q):
    return (x * x - y * y) % q


def Q(x, y, q):
    return ((x - y) * (x + y)) % q


for r in [1, 3, 5]:
    print('BPP, повторов', r,
          'ошибка', oshibka_bolshinstva(r, Fraction(1, 3)))
for r in [1, 3, 5]:
    print('RP, повторов', r, 'пропуск', Fraction(1, 2) ** r)
q = 7
nulej = sum(x * y % q == 0 for x in range(q) for y in range(q))
print('xy: нулевых подстановок', nulej, 'из', q * q)
print('граница Шварца-Зиппеля:', Fraction(2, q))
print('x²-y² = (x-y)(x+y):',
      all(P(x, y, q) == Q(x, y, q)
          for x in range(q) for y in range(q)))
print('x^q-x нулевой как функция:',
      all((x ** q - x) % q == 0 for x in range(q)))

BPP, повторов 1 ошибка 1/3
BPP, повторов 3 ошибка 7/27
BPP, повторов 5 ошибка 17/81
RP, повторов 1 пропуск 1/2
RP, повторов 3 пропуск 1/8
RP, повторов 5 пропуск 1/32
xy: нулевых подстановок 13 из 49
граница Шварца-Зиппеля: 2/7
x²-y² = (x-y)(x+y): True
x^q-x нулевой как функция: True

У ненулевого xy степень два; ноль получится, если хотя бы одна переменная равна нулю. Это 7 + 7 − 1 = 13 подстановок из 49. Граница 2/7 = 14/49 верна, хотя не достигается точно. Для тождества разность всегда нулевая; случайной ошибки в эту сторону нет.

Разбор: один seed не даёт пяти попыток

Пусть RP промахивается на половине случайных строк. Пять независимых строк дают вероятность пяти промахов 1/32. Если перед каждым запуском установить одно и то же зерно генератора, программа получит одну и ту же строку пять раз. Вероятность промаха останется 1/2. Перезапуск процесса не равен независимому испытанию: важен источник случайных битов.

Что ломается без этого

Средняя точность по тестовым входам не доказывает принадлежность BPP: может существовать вход, где ошибка почти единица. Таймаут ZPP не является достоверным ответом «нет». Успех RP на одном входе не означает, что все ответы «нет» стали верными. Эти ошибки относятся к договору программы с вызывающим кодом, а не к размеру выборки тестов.

Зачем это в работе

При сравнении символических выражений, вероятностном поиске и алгоритмах без гарантированной длительности нужно решить, что делать после неудачи: повторить, проверить сертификат, переключиться на точный алгоритм или вернуть вероятностный ответ. Классы дают язык для этого решения. Они не заменяют оценку стоимости арифметики: операции над большими числами тоже должны укладываться в обещанное время.

Теперь сам

У RP вероятность ложного «нет» не больше половины. Сколько независимых запусков достаточно, чтобы она стала не больше 1/1024, если принять при любом «да»?