Beweis, dass wenn p= pspace, rp= bpp
Frage
wie der Titel sagt.Ich kann nicht herausfinden, wie er sich beweisen kann.
Ich denke, es muss wahrscheinlich mit der Polynomhierarchie zusammenbrechen, aber ich bin mir nicht sicher.
Lösung
$ P \ Subseteq RP $ , $ BPP \ Subseteq pspace $ .
so $ pspace \ subseteq p $ , $ -> $ $ BPP \ Subseteq RP $ .
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit cs.stackexchange