ZPP (Komplexitätsklasse)

ZPP (Komplexitätsklasse)

Die Komplexitätsklasse ZPP oder ZPP(\epsilon(n)) (Zero-error Probabilistic Polynomial Time) beinhaltet alle Probleme, für die es eine nichtdeterministische Turingmaschine, die an jeder Stelle mit gleicher Wahrscheinlichkeit unter den möglichen Alternativen auswählt, mit folgenden Eigenschaften gibt:

  • 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 einer durch \epsilon(n) begrenzten Wahrscheinlichkeit statt der richtigen Antwort keine Antwort (also ein "Weiß nicht") zurückgibt. Die beiden Definitionen sind also äquivalent, wie sich mathematisch zeigen lässt.

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.


Wikimedia Foundation.

Игры ⚽ Поможем написать курсовую

Schlagen Sie auch in anderen Wörterbüchern nach:

  • ZPP — steht als Abkürzung für: ZPP (Komplexitätsklasse), Komplexitätsklasse ein Gemisch für Feststoffraketen, siehe Anfeuerungssatz Związek Patriotów Polskich (Bund polnischer Patrioten), eine moskautreue polnische Exilantenorganisation in der UdSSR …   Deutsch Wikipedia

  • Co-RP (Komplexitätsklasse) — co RP (random polynominal) bzw. co RP(ε(n)) bezeichnet die Klasse der Entscheidungsprobleme, für die es einen randomisierten Algorithmus mit polynomineller maximaler Rechenzeit gibt, der jede zu akzeptierende Eingabe mit Wahrscheinlichkeit 1… …   Deutsch Wikipedia

  • RP (Komplexitätsklasse) — RP (random polynomial) bzw. RP( (n)) bezeichnet die Klasse der Entscheidungsprobleme, für die es einen randomisierten Algorithmus A mit polynomieller Laufzeit gibt, der jede nicht zu akzeptierende Eingabe mit Wahrscheinlichkeit 1 ablehnt und für… …   Deutsch Wikipedia

  • Co-RP — (random polynominal) bzw. co RP( (n)) bezeichnet die Klasse der Entscheidungsprobleme, für die es einen randomisierten Algorithmus mit polynomineller maximaler Rechenzeit gibt, der jede zu akzeptierende Eingabe mit Wahrscheinlichkeit 1 annimmt… …   Deutsch Wikipedia

  • Komplexitätstheorie — Die Komplexitätstheorie als Teilgebiet der Theoretischen Informatik befasst sich mit der Komplexität von algorithmisch behandelbaren Problemen auf verschiedenen mathematisch definierten formalen Rechnermodellen. Die Komplexität von Algorithmen… …   Deutsch Wikipedia

  • Liste von Komplexitätsklassen — Dies ist eine Liste von Komplexitätsklassen, die in der Komplexitätstheorie betrachtet werden. Die Klassen verwenden in ihren Definitionen verschiedene Maschinenmodelle. Die wichtigsten Modelle sind Turingmaschinen; diese können deterministisch,… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”