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

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

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

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

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

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

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

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

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

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

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

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

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

Посилання