PP klass

I komplexitetsteorin är PP en klass av problem som kan lösas av probabilistiska Turing-maskiner i polynomtid, med en felsannolikhet på mindre än 1/2. Förkortningen PP står för Probabilistic Time Polynomial.

Definition

Ett språk L tillhör PP om och bara om det finns en probabilistisk Turingmaskin M sådan att

• M är polynom i tid
• För alla x från L returnerar M 1 med sannolikhet som är strikt större än 1/2
• För alla x som inte är i L , returnerar M 1 med sannolikhet högst 1/2

PP och BPP

BPP - klassen är en delmängd av PP -klassen ; det kan betraktas som en delmängd av problem för vilka effektiva probabilistiska algoritmer finns tillgängliga. Skillnaden ligger i storleken på felsannolikheten: i BPP -klassen måste vilken algoritm som helst ge rätt svar med en sannolikhet större än c (c > 1/2), såsom 2/3 eller 777/1000. I det här fallet kan man köra algoritmen ett fast antal gånger och sedan välja svaret med flest röster för att uppnå en viss korrekthetssannolikhet mindre än 1. Antalet repetitioner ökar när c närmar sig 1/2, men beror inte på n .

Kommentar. c kan inte vara beroende av en ingång. Å andra sidan kan algoritmen från PP göra följande sekvens av åtgärder:

• Om det korrekta svaret är "Ja", säger algoritmen "Ja" med sannolikheten 1/2+1/2 n , där n är längden på inmatningen.
• Om det korrekta svaret är "Nej", säger algoritmen "Ja" med en sannolikhet på 1/2-1/2 n .

Eftersom dessa två möjligheter är ganska nära, speciellt för stora n , är det, även om Turing-maskinen körs ett stort antal gånger, mycket svårt att förstå om vi arbetar med alternativet där det korrekta svaret är "Ja" eller "Nej" . Att försöka uppnå ett fast sannolikhetsvärde med en majoritetsröst kräver ett antal repetitioner som är exponentiella i n . Grovt sett kan detta jämföras med uppgiften att avgöra vilken sida ett mynt kommer att falla med liten marginal genom att kasta det ett stort antal gånger.