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
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.
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.
Relació amb d'altres classes 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 ZPPZPP = ZPP.
S'ha demostrat que P està contingut dins de ZPP, i es conjectura que P = ZPP.
Referències
Categoria:Classes de complexitat