Ich bin ein wenig verwirrt. Eigentlich war ich überzeugt, mein Beweis passt schon so, aber ein wenig Unklarheit bleibt. Fangen wir also an:

Die Klassen mit der Fehlerfunktion sind so definiert, dass genau dann gilt, wenn es einen randomisierten Algorithmus gibt, so dass folgende Eigenschaften gelten:

1. macht keine fälschlicherweise positiven Aussagen.
2. macht fälschlicherweise negative Aussagen mit einer Wahrscheinlichkeit, die kleiner gleich ist, wobei die Eingabe ist.
3. Korrekte positive Aussagen macht also mit einer Wahrscheinlichkeit größer gleich
4. Die Laufzeit von ist unabhängig vom Zufallsband der entsprechenden Turingmaschine polynomiell beschränkt durch , wobei irgendein Polynom ist.

Definieren wir nun als die Vereinigung aller möglichen Klassen , dann gilt . Meinen Beweis lasse ich jetzt mal weg, ich erläutere nur mal mein Problem: Wenn ich es richtig verstehe, ist ja, wenn man Konstanten als Fehlerfunktionen verwendet, immer .

Erste Frage: Wenn ich nun betrachte, ist das dann nicht gleich dasselbe wie ? Müsste es doch, denn hier sind alle Fehlerwahrscheinlichkeiten erlaubt.

Jetzt das Hauptproblem: Betrachte ich , dann sind dort also auch alle Sprachen enthalten, für die nur ein randomisierter Algorithmus existiert, der immer falsche negative Aussagen macht, also die Wörter der Sprache nie akzeptiert. Per Definition ist aber eine Sprache doch nur dann in , wenn es einen Automaten gibt, der für jedes Wort der Sprache mindestens über eine nichtdeterministisch zu wählende Konfigurationsfolge verfügt, die zum Akzeptieren des Wortes führt. Werden aber immer falsche negative Aussagen gemacht, dann wird das Wort nie akzeptiert – wie kann also gelten?

Wo liegt mein Fehler?

Update: Nachdem ich ein wenig nachgeforscht habe, vermute ich einfach, dass der Fehler letztlich in nem fehlerhaften Tafelan- oder abschrieb liegt: Macht man aus dem der Fehlerfunktion zugeordneten Intervall ein halboffenes (nämlich genau , dann ergibt alles wieder einen Sinn (nur dass die 1 dann da irgendwie nicht stehen kann).

Update 2: Der Fehler war tatsächlich der genannte. Offensichtlich auch nach Tafelanschrieb musste es heißen (wobei ich nicht ganz sehe, warum die 0 nicht mit drin sein sollte). gibts dann wohl nur “per Definition” ;)