Die Komplexitätsklasse ZPP (englisch zero-error probabilistic polynomial time) beinhaltet alle Probleme, für die es eine nichtdeterministische Turingmaschine gibt, die an jeder Stelle mit gleicher Wahrscheinlichkeit unter den möglichen Alternativen auswählt und folgende Eigenschaften besitzt:
- Sie gibt immer die richtige Antwort zurück (daher "zero-error")
- Die Laufzeit ist nicht begrenzt, jedoch existiert ein Polynom, durch das die mittlere Laufzeit begrenzt ist
Der randomisierte Algorithmus ist also korrekt, kann aber mitunter eine sehr viel längere Laufzeit als im typischen Fall haben.
Für alle Probleme aus ZPP existiert auch eine probabilistische Turingmaschine, die immer eine polynomial begrenzte Laufzeit hat, dafür aber mit Wahrscheinlichkeit kleiner 1/2 statt der richtigen Antwort keine Antwort (also ein „weiß nicht“) zurückgibt. Die beiden Definitionen sind also äquivalent.
Definiert wird ZPP meist als Schnittmenge von RP und co-RP. Diejenigen Probleme, für die Las-Vegas-Algorithmen mit mittlerer polynomialer Laufzeit existieren, liegen in ZPP.
ZPP wurde mit anderen probabilistischen Komplexitätsklassen 1977 von John T. Gill eingeführt.
Eigenschaften Bearbeiten
ZPP ist abgeschlossen unter Komplementbildung, Vereinigung und Schnitt. Das bedeutet, dass für zwei Sprachen auch . Es ist also co-ZPP = ZPP.
Es ist kein ZPP-vollständiges Problem bekannt und es gibt Hinweise darauf, dass es keine ZPP-vollständigen Probleme gibt.
Einzelnachweise Bearbeiten
- Daniel Pierre Bovet und Pierluigi Crescenzi: Introduction to the Theory of Complexity. Prentice Hall, 1994, ISBN 0-13-915380-2, S. 195.
- Daniel Pierre Bovet und Pierluigi Crescenzi: Introduction to the Theory of Complexity. Prentice Hall, 1994, ISBN 0-13-915380-2, S. 198,202.
Weblinks Bearbeiten
- ZPP. In: Complexity Zoo. (englisch)