Monimutkaisuusteoriassa PP on luokka ongelmia , jotka voidaan ratkaista todennäköisyyspohjaisilla Turingin koneilla polynomiajassa virhetodennäköisyydellä alle 1/2. Lyhenne PP on lyhenne sanoista Probabilistic Time Polynomial.
Kieli L kuuluu PP :hen silloin ja vain, jos on olemassa todennäköisyyspohjainen Turingin kone M
BPP - luokka on PP -luokan osajoukko ; sitä voidaan pitää ongelmien osajoukkona, jolle on saatavilla tehokkaita todennäköisyysalgoritmeja. Ero on virhetodennäköisyyden suuruudessa: BPP -luokassa minkä tahansa algoritmin on annettava oikea vastaus todennäköisyydellä, joka on suurempi kuin c (c > 1/2), kuten 2/3 tai 777/1000. Tässä tapauksessa voidaan suorittaa algoritmi tietyn määrän kertoja ja valita sitten eniten ääniä saanut vastaus, jotta saavutetaan tietty todennäköisyys, joka on pienempi kuin 1. Toistojen määrä kasvaa c :n lähestyessä arvoa 1/2, mutta se ei riipu n .
Kommentti. c ei voi olla riippuvainen syötteestä. Toisaalta PP :n algoritmi voi tehdä seuraavan toimintosarjan:
Koska nämä kaksi mahdollisuutta ovat varsin lähellä toisiaan, varsinkin suurelle n :lle , vaikka Turingin konetta ajettaisiin useita kertoja, on erittäin vaikea ymmärtää, onko kyseessä vaihtoehto, jossa oikea vastaus on "Kyllä" vai "Ei". . Kiinteän todennäköisyysarvon saavuttaminen enemmistöäänestyksellä vaatii useita toistoja, jotka ovat eksponentiaalisia n :ssä . Karkeasti tätä voidaan verrata tehtävään määrittää, kummalle puolelle koliko putoaa pienellä marginaalilla heittämällä sitä monta kertaa.
| Algoritmien monimutkaisuusluokat | |
|---|---|
| Kevyenä pidetty | |
| Taitaa olla vaikeaa | |
| Vaikeaksi pidetty |
|