Diskussion:RP (Komplexitätsklasse)
Zur Navigation springen
Zur Suche springen
RP(1) = RP*
[Quelltext bearbeiten]Hallo allerseits,
RP(1) = RP* wirkt auf mich falsch. In Wegners "Komplexitätstheorie" wird RP* als als Vereinigung aller möglich Fehlerwahrscheinlichkeiten < 1 angegeben. Auf <= wird explizit verzichtet. Das steht also im Widerspruch zu der Aussage im Artikel. Oder ist das eine definierte (allgemein bekannte) Schreibweise?
Aus meiner Sicht wäre folgendes korrekt: RP(e(n)) = RP* wobei e(n) < 1 sein muss. e (oder Epsilon) ist dann die Fehlerwahrscheinlichkeit bei einer Eingabe der Länge n.
Beste Grüße Benedikt (nicht signierter Beitrag von 89.0.65.105 (Diskussion) 09:13, 7. Jul 2011 (CEST))