נגדיר את ZPP כמחלקת השפות A שעבורן קיימת מכונת טיורינג הסתברותית M וקיים פולינום p, כך שלכל x,

נגדיר את $ZPP$ כמחלקת השפות $A$ שעבורן קיימת מכונת טיורינג הסתברותית $M$ וקיים פולינום $p$, כך שלכל $x$,

$$E[time_M(x)]\le p(|x|).$$

כלומר, תוחלת זמן הריצה של $M$ על $x$ פולינומית ב-$|x|$, אך אין הבטחה לגבי זמן הריצה הגרוע ביותר. כמו כן, לכל $x$, בכל ריצה שבה $M$ עוצרת על $x$, היא מחזירה את התשובה הנכונה.

הראו כי

$$ZPP=RP\cap coRP.$$

רמז: אי־שוויון מרקוב.