Apakah RNC seragam terdapat di ruang polylog?

Log-space-uniform NC terkandung dalam ruang polylog deterministik (kadang-kadang ditulis PolyL). Apakah log-space-uniform RNC juga ada di kelas ini? Versi acak standar dari PolyL harus dalam PolyL, tapi saya tidak melihat bahwa (seragam) RNC berada di dalam Random-PolyL.

Kesulitan yang saya lihat adalah bahwa di RNC, rangkaian dapat "melihat bit acak" sebanyak yang diinginkan; yaitu, input acak dapat memiliki fanout sewenang-wenang. Tetapi dalam versi acak PolyL, itu tidak seperti Anda mendapatkan rekaman bit acak yang bisa Anda lihat sebanyak yang Anda inginkan; alih-alih, Anda hanya diperbolehkan melempar koin pada setiap langkah waktu.

Terima kasih!

Mungkin kebanyakan orang berpikir bahwa (atau bahkan R N C = N C ), tetapi saya ragu tentang ini (lihat bagian kedua dari saya jawab, di bawah). Jika R N C memang terkandung dalam D S P A C E ( p o l y l o g ) , maka itu juga terkandung dalam $\mathsf{RNC}\subseteq \mathsf{DSPACE(polylog)}$$\mathsf{RNC}=\mathsf{NC}$$\mathsf{RNC}$$\mathsf{DSPACE(polylog)}$ (lebih khusus lagi, ada di D T I M E ( 2 p o l y l o g ) dengan pencarian lengkap).$\mathsf{NTIME(2^{polylog})}$$\mathsf{DTIME(2^{polylog})}$

Valentine Kabanets menjelaskan kepada saya argumen (cerita rakyat) berikut dari makalahnya dengan Russell Impagliazzo yang menjelaskan mengapa tidak mungkin.$\mathsf{RNC} \subseteq \mathsf{NTIME(2^{polylog})}$

Teorema: Jika , maka N E X P tidak dapat dihitung oleh sirkuit Boolean dengan ukuran o ( 2 n / n ) (yaitu sub-maksimalisasi oleh Shannon; tidak relevan tetapi lihat Lupanov untuk keketatan), atau Permanen tidak dapat dihitung dengan rumus aritmatika (pembagian-bebas) di atas Z dengan ukuran kuasipolinomial.$\mathsf{RNC}\subseteq \mathsf{NTIME(2^{polylog})}$$\mathsf{NEXP}$$o(2^n/n)$${\mathbb Z}$

Bukti: asumsikan . Jika Permanen memiliki formula ukuran quasipolynomial, maka kita dapat menebak dan memverifikasi formula seperti itu untuk Permanen menggunakan tester identitas polinomial waktu quasipolynomial dengan asumsi. Ini menempatkan Permanen dalam N T I M E ( 2 p o l y l o g ) .$\mathsf{RNC}\subseteq \mathsf{NTIME(2^{polylog})}$$\mathsf{NTIME(2^{polylog})}$

Dengan teorema Toda, kemudian juga dalam N T I M E ( 2 p o l y l o g ) . Dengan padding, versi waktu linear-eksponensial dari Σ 5 juga di N E X P . Oleh karena itu versi linear-eksponensial dari Σ 5 memiliki rangkaian ukuran o ( 2 n / n ) (yaitu submax). Tetapi, dengan argumen diagonalisasi sederhana, seseorang dapat menunjukkan bahwa versi linear-eksponensial dari Σ $\Sigma_2$$\mathsf{NTIME(2^{polylog})}$$\Sigma_5$$\mathsf{NEXP}$$\Sigma_5$$o(2^n/n)$$\Sigma_5$membutuhkan ukuran sirkuit maks, yang merupakan kontradiksi (omong-omong, ini adalah varian dari pertanyaan tingkat menengah untuk kursus tingkat kompleksitas lulusan; oke, mungkin membuktikan bahwa membutuhkan sirkuit max-size lebih sederhana). QED.$\mathsf{EXPSPACE}$

Sekarang arahnya tidak populer.

$\mathsf{RNC}$

(Ada juga beberapa makalah lain, seperti kertas Noam Nisan yang luar biasa tentang read-once vs read-many randomness, yang menunjukkan cara membeli kesalahan dua sisi dengan kesalahan satu sisi.)

Ngomong-ngomong, memahami bagaimana membangun PRG membodohi model perhitungan ruang-terbatas dengan akses ganda ke input mereka (misalnya Bps linear panjang) juga sangat terkait dengan pertanyaan ini.

- Periklis