Клас складності 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/2ⁿ, де n — це довжина входу.
• Якщо правильна відповідь «Ні», алгоритм каже «Так» з імовірністю 1/2-1/2ⁿ.

Оскільки ці дві можливості досить близькі, особливо для великих n, навіть якщо машину Тюрінга запустити багато разів, дуже складно зрозуміти, чи працюємо ми з варіантом, де правильна відповідь «Так», чи «Ні». Спроба домогтися фіксованого значення ймовірності, використовуючи більшість голосів, вимагає кількості повторень, експоненційної за n. Грубо, це можна порівняти із задачею визначення, якою стороною випаде монета з невеликою перевагою, підкидаючи її багато разів.