Fachrat Informatik - Forum

Hallo,

ich habe die Prüfung schon seit Anfang Februar hinter mir. Wahrscheinlich hast Du drauf gehofft, dass ich Dir jetzt einiges sage, was Du nicht lernen musst. Aber da muss ich Dich enttäuschen.
Es wird quer durch das ganze Skript von der ersten bis zur letzten Vorlesung gefragt. Und wenn Du eine 1 vorm Komma haben willst, solltest Du unbedingt auch einen Plan von den Beweisen haben.

Also dann viel Spaß beim Lernen. Ist wirlklich ne ganze Menge. Aber Prof. Vollmer ist ja kein Unmensch und hilft auch weiter, wenn man nicht mehr weiter weiß.
Wenn man sich gut vorbereitet hat, ist die Prüfung ok. Aber das ist wohl fast immer so ;-)

Mir ist bei dem o.g. Beweis nicht ganz klar wieso man die Menge B' benutzt. Der einzige Grund der mir einfällt, ist der, daß es dann möglich ist eine Abschätzung der Wahrscheinlichkeit über |x| zu formulieren, die letztlich dann zu der letzten Abschätzung von 2/3 führt.

Ist das korrekt, oder habe ich etwas grundlegenderes bei dem Beweis nicht verstanden?

Quoted

Original von Banshee
Mir ist bei dem o.g. Beweis nicht ganz klar wieso man die Menge B' benutzt. Der einzige Grund der mir einfällt, ist der, daß es dann möglich ist eine Abschätzung der Wahrscheinlichkeit über |x| zu formulieren, die letztlich dann zu der letzten Abschätzung von 2/3 führt.

Ist das korrekt, oder habe ich etwas grundlegenderes bei dem Beweis nicht verstanden?

Genau. Um zu zeigen, daß BPP^BPP = BPP gilt, simuliert man das verwendete BPP-Orakel durch eine BPP-Maschine. Um bei dieser Simulation in Sachen Laufzeit nicht von den konkreten Orakelfragen abhängig zu sein, fordert man, daß die Eingabe der ursprünglichen Maschine immer Teil der Orakelfragen ist.