Null-Fehler probabilistische polynomielle Zeit

Einfache Sprache

Eine probabilistic Turing machine läuft in Null-Fehler probabilistische polynomielle Zeit bzw. liegt in $\mathbf{ZPP}$, falls sie in polynomieller Zeit mit einer Fehlerwahrscheinlichkeit von $0$ akzeptiert oder verwirft, aber es besteht auch die Möglichkeit das sie weder akzeptiert noch verwirft.

Def. Null-Fehler probabilistische polynomielle Zeit

$\mathbf{ZPP}$ ist die Klasse der Sprachen, sowohl in RP als auch in coRP sind.