Apakah generator pseudo-random Nisan relativize?

16

Nisan membuktikan dalam "Psuedorandom Generator untuk Space-Bounded Computation", bahwa ada generator pseudo-acak yang "membodohi" perhitungan yang dibatasi ruang. Apakah konstruksi ini berlaku untuk setiap oracle (setidaknya untuk permintaan non-adaptif)?

cc.complexity-theory space-bounded derandomization Sebastian Ben Daniel
sumber
Saya tidak dapat menjawab pertanyaan ini, namun saya ingin menunjukkan makalah terkait berjudul "Kekerasan vs Keacakan" ( dx.doi.org/10.1016/S0022-0000(05 ) 80043-1 ), yang mungkin berguna bagi Anda.
MS Dousti

Jawaban:

18

Itu tergantung pada apakah dalam definisi Anda tentang Oracle TM, pita permintaan oracle juga terikat dengan ukuran logaritmik: jika dibatasi maka PRG juga membodohi L ^ A untuk setiap A juga, jika tidak dibatasi maka A dapat berisi daftar "string pseudorandom" dan dengan demikian L ^ A tidak akan tertipu.

Noam
sumber
Ini berlaku untuk semua generator pseudo-acak, namun, misalnya, generator NW melakukan relativizies jika kita mengasumsikan kekerasan terhadap oracle yang ingin kita menipu. Saya bertanya-tanya apakah kita bisa melakukan sesuatu seperti ini juga untuk generator ini.
Sebastian Ben Daniel
5
Karena PRG ini benar-benar ditentukan (mis. Tidak didasarkan pada beberapa "hard function f" lainnya), tidak jelas bagaimana menggunakan oracle dalam pengaturan relativized.
Noam