Diskussion:ZPP (Komplexitätsklasse)

Versagenswahrscheinlichkeit

Bin extra hierhergekommen, um Gewissheit zu erlangen, doch jetzt bin ich verwirrter als zuvor. Handelt es sich bei der Angabe der Versagenswahrscheinlichkeit um ein kleiner oder höchstens? Im Einleitungssatz steht kleiner. Im Artikel zu BPP sowie RP heißt es jeweils höchstens. Im Buch "Komplexitätstheorie-Grenzen der Effizienz von Algorithmen" heißt es auf Seite 35 letzter Satz ebenfalls höchstens. Dort steht: "Ein ZPP(1/2)-Algorithmus ist wie ein Münzwurf, bei dem wir bei Zahl, also mit einer Wahrscheinlichkeit von (höchstens) 1/2, verlieren." Zwei Seiten weiter wird behauptet: "Ein algorithmisches Problem gehört zur Komplexitätsklasse ZPP, wenn es zu ZPP(1/2) gehört, es also einen randomisierten Algorithmus mit polynomieller maximaler Rechenzeit gibt, der niemals falsche Ergebnisse liefert und für jede Eingabe eine durch 1/2 beschränkte Versagenswahrscheinlichkeit hat." In Theorem 3.3.8. auf Seite 39 steht dann (beide Aussagen zusammenführend) ZPP = ZPP(1/2).

Ich freue mich auf eure Antwort. --Wisdom The Wizard (Diskussion) 09:56, 7. Feb. 2022 (CET)