Клас складності PP
В теорії складності, PP є класом задач, розв'язуваних імовірнісними машинами Тюрінга за поліноміальний час, з імовірністю помилки менше 1/2. Абревіатура PP позначає «імовірнісний поліноміальний за часом».
Визначення
Мова L належить PP тоді й лише тоді, коли існує імовірнісна машина Тюрінга M така, що
- M поліноміальна за часом
- Для будь-якого x з L, M повертає 1 з імовірністю строго більшою 1/2
- Для будь-якого x не з L, M повертає 1 з імовірністю не більшою 1/2
PP і BPP
Клас BPP є підмножиною класу PP; його можна розглядати як підмножину задач, для яких є ефективні імовірнісні алгоритми. Різниця полягає у величині ймовірності помилки: в класі BPP, будь-який алгоритм повинен дати правильну відповідь з імовірністю більше, ніж c (c > 1/2), наприклад 2/3 або 777/1000. У цьому випадку, можна запустити алгоритм фіксовану кількість разів, а потім вибрати відповідь, що має більшість голосів, щоб досягти певної ймовірності коректності менше 1. Кількість повторень збільшується при наближенні c до 1/2, але не залежить від n.
Зауваження. c не може залежати від входу. З іншого боку, алгоритм з PP може виконувати таку послідовність дій:
- Якщо правильна відповідь «Так», алгоритм каже «Так» з імовірністю 1/2+1/2n, де n — це довжина входу.
- Якщо правильна відповідь «Ні», алгоритм каже «Так» з імовірністю 1/2-1/2n.
Оскільки ці дві можливості досить близькі, особливо для великих n, навіть якщо машину Тюрінга запустити багато разів, дуже складно зрозуміти, чи працюємо ми з варіантом, де правильна відповідь «Так», чи «Ні». Спроба домогтися фіксованого значення ймовірності, використовуючи більшість голосів, вимагає кількості повторень, експоненційної за n. Грубо, це можна порівняти із задачею визначення, якою стороною випаде монета з невеликою перевагою, підкидаючи її багато разів.