Clasa PP

În teoria complexității , PP este o clasă de probleme rezolvabile de mașinile Turing probabilistice în timp polinomial, cu o probabilitate de eroare mai mică de 1/2. Abrevierea PP înseamnă probabilistic Time Polynomial.

Definiție

Un limbaj L aparține lui PP dacă și numai dacă există o mașină de Turing probabilistică M astfel încât

• M este polinom în timp
• Pentru orice x din L , M returnează 1 cu probabilitate strict mai mare decât 1/2
• Pentru orice x care nu este în L , M returnează 1 cu probabilitatea de cel mult 1/2

PP și BPP

Clasa BPP este un subset al clasei PP ; poate fi considerată ca un subset de probleme pentru care sunt disponibili algoritmi probabilistici eficienți. Diferența constă în mărimea probabilității de eroare: în clasa BPP , orice algoritm trebuie să dea răspunsul corect cu o probabilitate mai mare decât c (c > 1/2), cum ar fi 2/3 sau 777/1000. În acest caz, se poate rula algoritmul de un număr fix de ori și apoi se alege răspunsul cu cele mai multe voturi pentru a obține o anumită probabilitate de corectitudine mai mică de 1. Numărul de repetări crește pe măsură ce c se apropie de 1/2, dar nu depinde de n .

Cometariu. c nu poate depinde de o intrare. Pe de altă parte, algoritmul de la PP poate face următoarea secvență de acțiuni:

• Dacă răspunsul corect este „Da”, algoritmul spune „Da” cu probabilitatea 1/2+1/2 n , unde n este lungimea intrării.
• Dacă răspunsul corect este „Nu”, algoritmul spune „Da” cu o probabilitate de 1/2-1/2 n .

Deoarece aceste două posibilități sunt destul de apropiate, mai ales pentru n mare , chiar dacă mașina Turing este rulată de un număr mare de ori, este foarte greu de înțeles dacă lucrăm cu opțiunea în care răspunsul corect este „Da” sau „Nu”. . Încercarea de a obține o valoare fixă ​​a probabilității folosind un vot majoritar necesită un număr de repetări care este exponențial în n . Aproximativ, acest lucru poate fi comparat cu sarcina de a determina care parte va cădea o monedă cu o marjă mică, aruncând-o de mai multe ori.