I teorien om beregningskompleksitet er ZPP ( eng. zero-error probabilistic polynomial time - error-free probabilistic polynomial ) en klasse af problemer med svaret "Ja" eller "Nej", som der er en sandsynlig Turing-maskine til , der opfylder følgende egenskaber:
Der er et alternativt sæt egenskaber:
Valg af et af de to sæt egenskaber resulterer i ækvivalente ZPP-klassedefinitioner. En Turing-maskine, der opfylder disse egenskaber, omtales nogle gange som en Turing-maskine af Las Vegas-typen .
ZPP - klassen er lig med skæringspunktet mellem RP- og Co-RP- klasserne . Dette tages ofte som definitionen af ZPP . For at demonstrere dette skal du bemærke, at ethvert problem, der hører til både RP og co-RP, har en Las Vegas -type algoritme :
Bemærk, at kun én af algoritmerne A eller B kan give et forkert svar, og sandsynligheden for denne hændelse er 50 % ved hvert trin. Sandsynligheden for at nå det k . trin falder således eksponentielt i forhold til k . Dette viser, at den forventede køretid er polynomiel. Det følger af det nævnte, at skæringspunktet mellem klasserne RP og co-RP er indeholdt i ZPP .
Lad os vise, at ZPP er indeholdt i skæringspunktet mellem RP og co-RP . Lad der være en Las Vegas-type Turing-maskine C , der løser problemet. Lad os betegne den matematiske forventning til tidspunktet for dens drift som M (ved betingelsen er den endelig). Så kan vi konstruere følgende RP- algoritme:
Sandsynligheden for, at svaret modtages før standsningsøjeblikket, er lig med ½ (fra Markovs ulighed ). Dette betyder igen, at sandsynligheden for at svare "Nej" med det rigtige svar "Ja" (dette kan ske på grund af det for tidlige stop af C ) er ½, hvilket opfylder definitionen af RP . For at bevise inklusion af ZPP i co-RP kan man enten bruge samme ræsonnement eller observere, at ZPP er lukket for komplementar.
| Kompleksitetsklasser af algoritmer | |
|---|---|
| Betragtes som lys | |
| Formodes at være svært | |
| Anses for vanskelig |
|