Clasa ZPP

În teoria complexității de calcul, ZPP ( eng. zero-error probabilistic polynomial time - error-free probabilistic polynom ) este o clasă de probleme cu răspunsul „Da” sau „Nu”, pentru care există o mașină Turing probabilistică care satisface urmatoarele proprietati:

• Ea răspunde întotdeauna corect „Da” sau „Nu”.
• Așteptarea matematică a timpului de funcționare al unei anumite mașini Turing este polinomială (timpul de funcționare în sine poate fi infinit de mare).

Există un set alternativ de proprietăți:

• O mașină Turing funcționează întotdeauna în timp polinomial.
• Ea răspunde „Da”, „Nu” sau „Nu știu”.
• Răspunsul poate fi fie corect, fie „nu știu”.
• Dacă răspunsul corect este „Da”, mașina Turing răspunde „Da” cu o probabilitate de cel puțin ½.
• Dacă răspunsul corect este „Nu”, mașina Turing răspunde „Nu” cu o probabilitate de cel puțin ½.

Alegerea unuia dintre cele două seturi de proprietăți are ca rezultat definiții echivalente ale clasei ZPP. O mașină Turing care satisface aceste proprietăți este uneori denumită o mașină Turing de tip Las Vegas .

O definiție echivalentă în termeni de intersecție

Clasa ZPP este egală cu intersecția claselor RP și Co-RP . Aceasta este adesea considerată definiția ZPP . Pentru a demonstra acest lucru, rețineți că orice problemă care aparține atât RP , cât și co-RP are un algoritm de tip Las Vegas :

• Să presupunem că există un limbaj L recunoscut de un RP -algoritm A și un (posibil diferit de A ) co-RP- algoritm B .
• Să executăm un pas al algoritmului A pe secvența de intrare. Dacă se returnează „Da”, atunci răspunsul final trebuie să fie „Da”. În caz contrar, rulați un pas al algoritmului B cu aceeași intrare. Dacă el răspunde „Nu”, atunci răspunsul final ar trebui să fie „Nu”. Dacă niciuna dintre condițiile anterioare nu este îndeplinită, repetați acest pas.

Rețineți că doar unul dintre algoritmii A sau B poate da un răspuns incorect, iar probabilitatea acestui eveniment este de 50% la fiecare pas. Astfel, probabilitatea de a atinge pasul k scade exponențial în raport cu k . Aceasta arată că timpul de rulare așteptat este polinom. Din cele spuse rezultă că intersecția claselor RP și co-RP este cuprinsă în ZPP .

Să arătăm că ZPP este conținut în intersecția dintre RP și co-RP . Să existe o mașină Turing C de tip Las Vegas care rezolvă problema. Să notăm așteptarea matematică a timpului funcționării sale ca M (prin condiție, este finită). Apoi putem construi următorul algoritm RP :

• Să rulăm C pentru un timp nu mai mic de 2M . Dacă în acest timp C a primit un răspuns, îl returnăm. Dacă nu se primește niciun răspuns înainte de oprire, spunem „Nu”.

Probabilitatea ca răspunsul să fie primit înainte de momentul opririi este egală cu ½ (din inegalitatea lui Markov ). Aceasta, la rândul său, înseamnă că probabilitatea de a răspunde „Nu” cu răspunsul corect „Da” (acest lucru se poate întâmpla din cauza opririi premature a lui C ) este ½, ceea ce satisface definiția RP . Pentru a demonstra includerea ZPP în co-RP , se poate fie folosi același raționament, fie se poate observa că ZPP este închis sub luarea complementului.

Literatură

• J. Gill. Complexitatea computațională a mașinilor Turing probabilistice  //  Proceedings of the sixth annual ACM symposium on Theory of computing (STOC '74). - New York, NY, SUA: Association for Computing Machinery, 1974. - P. 91–95 . - doi : 10.1145/800119.803889 .