Клас складності BPP

В теорії алгоритмів класом складності BPP (від англ. bounded-error, probabilistic, polynomial) називається клас предикатів, які швидко (за поліноміальний час) обчислюються і дають відповідь з високою достовірністю (причому, жертвуючи часом, можна домогтися як завгодно високої точності відповіді). Задачі, які розв'язуються ймовірнісними методами і лежать в BPP, виникають на практиці дуже часто.

Формальне визначення

Класом BPP називається клас предикатів P(x), обчислюваних на імовірнісних машинах Тюрінга (звичайних машинах Тюрінга зі стрічкою випадкових чисел) за поліноміальний час з помилкою не більше ⅓. Це означає, що, обчислюючи значення предиката, імовірнісна машина Тюрінга дасть відповідь за час, що дорівнює O(n^k), де n — довжина x, причому якщо правильна відповідь 1, то машина видає 1 з імовірністю принаймні ⅔, і навпаки. Множина слів, на яких P(x) повертає 1, називається мовою, розпізнаваною предикатом P(x).

Число ⅓ у визначенні вибрано довільно: якщо замість нього вибрати будь-яке число p, строго менше від ½, то вийде той самий клас. Це правильно, оскільки, якщо є машина Тюрінга, що розпізнає мову з імовірністю помилки p за час O(n^k), то точність можна як завгодно добре поліпшити за рахунок відносно невеликого приросту часу. Якщо ми запустимо машину n разів поспіль, а за результат візьмемо результат більшості запусків, то ймовірність помилки впаде до $\left(2{\sqrt {p(1-p)}}\right)^{n}$, а час дорівнюватиме O(n^k+1). Тут n запусків машини розглядаються як схема Бернуллі з n випробувань та ймовірністю успіху 1-p, а формула, що виражає помилку, — ймовірність невдачі не менш ніж у половині випадків. Якщо тепер запустити машину n² разів підряд, то час зросте до O(n^k+2), а ймовірність помилки впаде до $\left(2{\sqrt {p(1-p)}}\right)^{n^{2}}$. Таким чином, із зростанням показника многочлена, оцінює час, точність зростає експоненціально, і можна досягти будь-якого потрібного значення.

Алгоритми Монте-Карло

Ймовірнісний алгоритм ${\mathcal {A}}$ приймає мову $L$ за стандартом Монте-Карло, якщо ймовірність помилки алгоритму не перевершує $1/3$. Тобто $\mathbb {P} ({\mathcal {A}}(x)=P(x))\geq 2/3$, де $P(x)$ — предикат належності слова $x$ мові $L$. Таким чином, клас BPP утворюють предикати такі що для них існує поліноміальний імовірнісний алгоритм, який приймає їх мову за стандартом Монте-Карло. Такі алгоритми називають алгоритмами Монте-Карло.

Відносини з іншими класами

Сам BPP замкнутий відносно доповнення. Клас P включений у BPP, оскільки він дає відповідь за поліноміальний час з нульовою помилкою. BPP включений у клас $\Sigma _{2}^{p}\cap \Pi _{2}^{p}$ поліноміальної ієрархії і, як наслідок, включений у PH і PSPACE. Крім того, відоме включення BPP в клас P/Poly.

Квантовим аналогом класу BPP (іншими словами, розширенням класу BPP на квантові комп'ютери) є клас BQP.

${\mbox{BPP}}\subseteq {\mbox{BQP}}$

Інші властивості

До 2002 року однією з найвідоміших задач, що лежать у класі BPP, була задача розпізнавання простоти числа, для якої існувало кілька різних поліноміальних імовірнісних алгоритмів, таких як тест Міллера-Рабіна, але жодного детермінованого. Однак, у 2002 році детермінований поліноміальний алгоритм знайшли індійські математики Аґравал, Каял і Саксена, які таким чином довели, що задача розпізнавання простоти числа лежить у класі P. Запропонований ними алгоритм AKS (названий за першими буквами їхніх прізвищ) розпізнає простоту числа довжини n за час O(n⁴).