В теорії алгоритмів класом складності 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 2 разів підряд, то час зросте до O (n k +2), а ймовірність помилки впаде до \ Left (2 \ sqrt {p (1-p)} \ right) ^ {n ^ 2} . Таким чином, зі зростанням показника многочлена, що оцінює час, точність зростає експоненціально, і можна досягти будь-якого потрібного значення.


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

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


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

\ Mbox {BPP} \ subseteq \ mbox {BQP}

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

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

Вважається легкими P L NL AC NC P-complete BQP BPP RP ZPP
Предпологаются складними NP ( co-NP NP-Complete Co-NP-complete) UP # P (# P-complete) IP PSPACE (PSPACE-complete) R PP AM
Вважається складними EXPTIME NEXPTIME EXPSPACE 2-EXPTIME PR RE Co-RE RE-complete Co-RE-complete PH
Список алгоритмів