Satz BPP teil von PSPACE
Einfache Sprache
Def. Satz BPP teil von PSPACE
$$\mathbf{BPP\in PSPACE}$$
Idee: Wir können die maximale mögliche Anzahl an Münzwurfschritten für eine Probabilistische Turingmaschine nach oben beschränken. Dann können wir alle möglichen Alternativen für die Münzwurfschritte simulieren. Letztendlich müssen wir nur die Anzahl der akzeptierenden durch die Anzahl aller möglichen Simulationen teilen, und erhalten so die Wahrscheinlichkeit das die probabilistische TM akzeptiert.
Beweis: Sei $M$ eine Probabilistische Turingmaschine die in polynomieller Zeit läuft. Wir können $M$ so modifizieren, dass $M$ exakt $n^r$ Münzwurfschritte in jeder möglichen Berechnung macht, wobei $r$ eine Konstante ist. Dann simuliert man alle möglichen Berechnungen und zählt wie viele akzeptieren. Falls mehr als $\frac{2}{3}2^{(n^r)}$ akzeptiert haben, akzeptiere, sonst verwerfe.