Dunia yang direlatifkan di mana

Saya ingin tahu apakah ada dunia yang direlatifikasi di mana . Saya juga tertarik untuk mengetahui apakah ada dunia yang direlatifikasi di mana .${\bf P^A}={\bf NP^A}\not = {\bf PP^A}$${\bf P^B} \not = {\bf NP^B} = {\bf PP^B}$

Saya tidak tahu referensi, tetapi saya pikir keduanya harus bisa dilakukan.

Untuk oracle pertama Anda: untuk pemula Anda akan menginginkan oracle (menyebutnya ) yang mengkodekan secara eksponensial-besar kasus, dan bahwa dengan demikian memisahkan kedua dan dari . Maka Anda ingin oracle kedua (sebut saja ) yang menyandikan solusi untuk semua masalah , dengan cara "terhuyung-huyung" sehingga mengakses tingkat hierarki memerlukan kueri ukuran (katakanlah) (dan karenanya Anda hanya bisa mendapatkan jumlah pergantian konstan dalam waktu polinomial). kedua ini akan menyebabkan . (Catat itu$A_1$$MAJORITY$$P^{A_1}$$NP^{A_1}$$PP^{A_1}$$A_2$$PH^{A_1}$$k^{th}$$n^k$$P^{A_1,A_2} = NP^{A_1,A_2} = PH^{A_1,A_2} = PH^{A_1}$$A_2$ hanyalah lapisan "luar", yang berarti bahwa setiap kueri ke dapat disimulasikan oleh permintaan .) Akhirnya, Anda akan ingin menarik batas bawah Yao dan Hastad's (yaitu, lemma switching ) untuk menunjukkan bahwa mesin masih tidak dapat memecahkan contoh di , dan karena itu (dan tentu ) tetap lebih besar.$A_2$ A C 0 P H A 1 M A J O R I T Y A 1 P P A 1 P P A 1 , A 2 = P P P H A $PH^{A_1}$$AC^0$$PH^{A_1}$$MAJORITY$$A_1$$PP^{A_1}$$PP^{A_1,A_2} = PP^{PH^{A_1}}$

Untuk oracle kedua Anda, Anda ingin membuat sedemikian rupa sehingga Anda perlu menyelesaikan masalah pencarian untuk "membuka" bagian dari string oracle yang kemudian meningkatkan daya Anda hingga ke . (Di sini kita mengeksploitasi fakta bahwa dan sama-sama ). Kehalusannya adalah bahwa bagian rahasia oracle tidak bisa hanya memutuskan bahasa lengkap yang tidak terkait - bahasa lengkap: ia juga perlu menyediakan jawaban untuk perhitungan yang menanyakan sendiri. Untungnya, diketahui cara mencapai itu secara bertahap, menghindari sirkularitas: pada dasarnya, Anda menyandikan output dari$B$$NP$$PSPACE$$NP^{PSPACE}$$PP^{PSPACE}$$PSPACE$$PSPACE$$PSPACE$$B$$PSPACE^B$ mesin yang hanya meminta pada input ukuran atau kurang, di bagian yang memerlukan kueri ukuran untuk mengakses, dan karena itu "di luar jangkauan" untuk mesin tersebut (tetapi bukan untuk lainnya mesin). Sementara itu, mesin dibiarkan "sepenuhnya dalam gelap" oleh semua ini.$B$$p(n)$$B$P S P A C E B P $>p(n)$ $PSPACE^B$$P^B$