PP jest przedmiotem teorii złożoności , dziedziną informatyki teoretycznej . Jest to klasa probabilistycznej złożoności. Dokładniej, jest to zbiór problemów decyzyjnych rozstrzyganych przez probabilistyczną maszynę Turinga w czasie wielomianowym z prawdopodobieństwem błędu mniejszym niż połowa.
Język L jest w PP, jeśli istnieje probabilistyczna maszyna Turinga M, taka że:
Klasy BPP i PP są bardzo podobne pod względem definicji, ale a priori nie są sobie równe. Rzeczywiście, BPP to klasa problemów, które mogą być rozwiązane przez maszynę w czasie wielomianowym z prawdopodobieństwem poprawnej odpowiedzi większym niż stała, która sama jest dokładnie większa niż 1/2. W związku z tym BPP jest uwzględniony w PP .
Mamy następujące dwa wtrącenia: NP jest zawarty w PP, który jest zawarty w PSPACE .
Twierdzenie Tody stwierdza, że P oracle PP zawiera PH , hierarchię wielomianów ( Toda 1991 ).
PP jest zamknięte związkiem i skrzyżowaniem ( Beigel, Reingold i Spielman 1991 ).
PP ma kompletne problemy, na przykład MAJSAT: dla formuły F maszyna musi zaakceptować wtedy i tylko wtedy, gdy F jest prawdziwe dla więcej niż połowy możliwych przypisań dla zmiennych.
Klasę tę wprowadził J. Gill w 1977 r. W artykule Złożoność obliczeniowa probabilistycznych maszyn Turinga , równolegle z klasami BPP , RP i ZPP ( Gill 1977 ).
Symetryczne zamykanie klasy różnic zostało zademonstrowane przez Davida Russo w swojej pracy magisterskiej, a zamknięcie związku i skrzyżowania zostało zademonstrowane w 1991 roku po tym, jak był to otwarty problem przez 14 lat.
Związek między PP a hierarchią wielomianów zdobył w 1998 roku Nagrodę Gödla dla Seinosuke Tody .