Hirarki Polinomial Acak?

Saya bertanya-tanya, apa yang akan terjadi, jika dalam definisi (Hirarki Polinomial, lihat, misalnya, di sini ), peran akan digantikan oleh ?N P R $PH$$NP$$RP$

Tampaknya, kita masih bisa membangun hierarki, dengan cara yang sama seperti dibangun, hanya menggunakan mana-mana, bukan , dan bukan . Mari kita menyebutnya Hirarki Polinomial Acak ( ).R P N P c o R P c o N P R P $PH$$RP$$NP$$coRP$$coNP$$RPH$

Tebakan pertama saya adalah , atau mungkin . Hal ini didasarkan pada fakta yang diketahui bahwa menyiratkan . Namun demikian, jika , maka masih bisa menjadi hierarki yang tepat dan tak terbatas dalam .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$

Tentu saja, tepi masalah ini tumpul oleh fakta bahwa ini menduga (bahkan ), yang akan meratakan ke . Namun, tidak diketahui saat ini, dan ia telah menolak semua upaya pembuktian sejauh ini. Oleh karena itu, masih memiliki setidaknya beberapa peluang untuk menjadi hierarki yang tepat.P = B P P R P H P P = R P R P $P=RP$$P=BPP$$RPH$$P$$P=RP$$RPH$

Sementara , diakui, memiliki peluang bagus untuk menjadi "datar," bisakah konsep itu masih berguna untuk sesuatu yang tidak penting? Berikut ini sebuah contoh: jika seseorang dapat membuktikan , maka akan menghasilkan bahwa menyiratkan , yang, saya pikir, akan menjadi hasil yang menarik.R P H = B P P P = R P P = B P $RPH$$RPH=BPP$$P=RP$$P=BPP$

Apakah ada yang diketahui tentang ini?

Jelas, . Di sisi lain, ( Buhrman & Fortnow , pdf ), jadi satu-satunya cara hierarki tidak runtuh ke (paling banyak) level kedua dan tidak habis akan karena alasan yang tidak mungkin bahwa oracle secara signifikan lebih lemah daripada .B P P = Z P P p r o m i s e R P B P P R P p r o m i s e R $\mathrm{RPH}\subseteq\mathrm{BPP}$$\mathrm{BPP}=\mathrm{ZPP^{promiseRP}}$$\mathrm{BPP}$$\mathrm{RP}$$\mathrm{promiseRP}$