В теорії складності, 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 (з> 1/2), наприклад 2/3 або 777/1000. У цьому випадку, можна запустити алгоритм фіксована кількість разів, а потім вибрати відповідь, що має більшість голосів, щоб досягти певної ймовірності коректності менше 1. Кількість повторень збільшується при наближенні c до 1/2, але не залежить від n.

Зауваження. C не може залежати від входу. З іншого боку, алгоритм з PP може проробляти наступну послідовність дій:

  • Якщо правильну відповідь "Так", алгоритм говорить "Так" з імовірністю 1/2 +1 / 2 n, де n - це довжина входу.
  • Якщо правильну відповідь "Ні", алгоритм говорить "Так" з вірогідністю 1/2-1/2 n.

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


Вважається легкими 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
Список алгоритмів