En teoria de la complexitat, la classe de complexitat ZPP (zero error probabilistic polynomial time) és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing probabilística tal que^[1][2]

• sempre retorna la resposta correcta, ja sigui SI o NO
• el temps d'execució és polinòmic per cada mida de l'entrada

Dit d'una altra manera, l'algorisme pot prendre decisions aleatòries. sempre retorna la resposta correcta i per un problema de mida n, de mitjana, el temps d'execució és menor d'un polinomi p(n) tot i que algunes execucions poden ser molt més llargues. A aquest tipus d'algorismes també se'ls coneix algorismes Las Vegas.^[3]

La definició de ZPP està basada en la màquina de Turing probabilística, com les definicions de les classes BPP i RP. La classe BQP també està basada en una màquina amb atzar com és el computador quàntic.

La classe ZPP és exactament igual a la intersecció de les classe RP i co-RP. Per tant, ZPP està dins de RP i de co-RP. De vegades es defineix la classe ZPP en funció d'aquesta intersecció.

Se sap que ZPP = co-ZPP i que ZPP^ZPP = ZPP.

S'ha demostrat que P està contingut dins de ZPP, i es conjectura que P = ZPP.