Randomisierte Polynomialhierarchie?

Ich frage mich, was passieren würde, wenn in der Definition von (Polynomialzeit - Hierarchie, siehe zB hier ), die Rolle von N P würde ersetzt durch R P ?$PH$$NP$$RP$

Es scheint, könnten wir noch eine Hierarchie aufzubauen, die gleiche Art und Weise wie aufgebaut ist, nur mit R P überall statt N P und c o R P anstelle von c o N P . Nennen wir es zufällige Polynom-Hierarchie ( R P H ).$PH$$RP$$NP$$coRP$$coNP$$RPH$

Meine erste Vermutung ist, dass oder vielleicht . Es basiert auf der bekannten Tatsache, dass impliziert . Wenn , dann könnte dennoch eine richtige, unendliche Hierarchie innerhalb von .R P H = B P P N P = R P P H = B P P P ≠ R P R P H B P $RPH\subseteq BPP$$RPH=BPP$$NP=RP$$PH=BPP$$P\neq RP$$RPH$$BPP$

Selbstverständlich ist der Rand der Ausgabe durch die Tatsache , dass abgestumpft gemutmaßt wird (auch P = B P P ), der flach wäre R P H in P . Jedoch P = R P ist zu diesem Zeitpunkt nicht bekannt, und es hat alle Beweisversuche bisher widerstanden. Daher R P H hat immer noch zumindest eine gewisse Möglichkeit , eine richtige Hierarchie zu sein.$P=RP$$P=BPP$$RPH$$P$$P=RP$$RPH$

Während , hat zwar eine gute Chance „flach“ zu sein , könnte das Konzept noch etwas nicht trivial nützlich sein? Hier ist ein Beispiel: Wenn man R P H = B P P beweisen kann, würde dies ergeben, dass P = R P P = B P P impliziert , was meines Erachtens ein interessantes Ergebnis wäre.$RPH$$RPH=BPP$$P=RP$$P=BPP$

Ist irgendetwas darüber bekannt?

Klar, . Auf der anderen Seite, B P P = Z P P P r o m i s e R P ( Buhrman & Fortnow , pdf ), so dass der einzige Weg , hat die Hierarchie nicht kollabieren die zweite Ebene (höchstens) und hat nicht die Abgas B P P wäre aus dem unwahrscheinlichen Grund, dass R P Orakel signifikant schwächer als P r o m i s e $\mathrm{RPH}\subseteq\mathrm{BPP}$$\mathrm{BPP}=\mathrm{ZPP^{promiseRP}}$$\mathrm{BPP}$$\mathrm{RP}$ orakel.$\mathrm{promiseRP}$