вує підкидання такої монети, будуть більше, ніж хотілося б; вона зможе обчислити і деякі нерозв'язні предикати. p align="justify"> Зазвичай вважають, що ймовірності випадання однакові для обох сторін монети, а результат підкидання ототожнюється з числом 0 або 1.
Хоча для ВМТ не можна сказати, який в точності відповідь вона видасть, можна визначити ймовірність того чи іншого відповіді.
Визначення 3.1. Предикат належить класу BPP, якщо існують такі ВМТ і поліном , що машина завідомо зупиниться за час, що не перевершує , причому
з імовірністю більшої дає відповідь "так";
з імовірністю більшої дає відповідь "ні".
Якщо в цьому визначенні замінити число на будь фіксоване число, більше , клас BPP не зміниться. Є простий спосіб домогтися ймовірності, як завгодно близькою до 1. Візьмемо кілька однакових машин, запустимо їх усі, а остаточним результатом будемо вважати думку більшості. Якщо ймовірність правильної відповіді для кожного екземпляра машини дорівнює , то можна довести, що ймовірність правильної відповіді після голосування машин не менше , де .
Зауваження 3.1. Уявити фізичну реалізацію НМТ дуже важко (згадаємо, що нам доведеться помістити в неї всезнайка Мерліна). А імовірнісні машини цілком можуть мислитися як реальні пристрої. Тому предикати з класу BPP цілком можна вважати реально вичіслімих. p align="justify"> Клас BPP можна визначити і за допомогою предикатів від двох змінних, як це було зроблено для класу NP.
Визначення 3.2. Предикат належить класу BPP, якщо існують такі поліном і предикат , що
частка слів довжини , для яких виконана , більше ;
частка слів довжини , для яких виконана , менше .
Теорема 3.1. Визначення 3.1 і 3.2 еквівалентні. p align="justify"> Доказ Опр. 3.1 Вважаємо (кількість підкидань монети не перевершує загального числа дій). Визначимо предикат ...
