Derandomisasi seragam kelas kompleksitas sirkuit

Biarkan menjadi kelas kompleksitas dan BP- C menjadi mitra acak dari didefinisikan dengan cara yang sama dengan didefinisikan sehubungan dengan . Lebih formal kami memberikan banyak bit acak polinomi dan kami menerima input jika probabilitas untuk menerima lebih dari .$\mathcal{C}$$\textrm{BP-}\mathcal{C}$$\mathcal{C}$$\textrm{BPP}$$\textrm{P}$$\frac{2}{3}$

Dalam posting sebelumnya , saya bertanya apakah diketahui apakah kesetaraan berlaku antara dan untuk kelas kompleksitas sirkuit. Jawabannya adalah ya untuk semua kelas kompleksitas yang cukup ekspresif untuk menghitung Mayoritas dan untuk karena beberapa alasan lain. Namun hasil itu tidak seragam dan saya ingin tahu:$\mathcal{C}$$\textrm{BP-}\mathcal{C}$$\mathcal{C}$$\textrm{AC}^0$

1. Apakah versi yang seragam dari hasil tersebut dipelajari atau diketahui? Adakah hasil parsial?

2. Apakah mereka menyiratkan dugaan lama?

Saya percaya bahwa derandomisasi seragam persis jadi saya berharap jawabannya adalah "ya" tetapi kurang jelas bagi saya apa dereragaman seragam kelas kecil dalam akan menyiratkan.$\textrm{P}/\textrm{poly}$$\textrm{P}=\textrm{BPP}$$\textrm{NC}$

Seragam kelas-RNC telah banyak dipelajari. Ini adalah masalah terbuka apakah uniform-RNC = uniform-NC. Uniform- (R) NC sesuai dengan (secara acak) PRAM dengan banyak prosesor secara polinomi dan waktu berjalan polylogarithmic (lihat Buku Pegangan Theoretical Computer Science Vol. A). Jadi pertanyaannya adalah apakah setiap algoritma paralel acak yang efisien dapat diderandomisasi.

Karena pengujian identitas penentu simbolis adalah seragam-RNC, derandomisasi RNC menyiratkan batas bawah sirkuit oleh hasil Kabanets & Impagliazzo (Kompleksitas Komputasi, 13 (1-2), halaman 1-46, 2004).

Kasus khusus yang penting adalah pertanyaan apakah kita dapat menghitung kecocokan sempurna dalam seragam-NC. Ada beberapa algoritma paralel acak yang diketahui, tetapi kami tidak tahu apakah ada yang deterministik. Baru-baru ini, Fenner, Gurjar dan Thierauf (STOC 2016) telah menunjukkan bahwa kita dapat menghitung kecocokan sempurna dalam grafik bipartit dengan sirkuit seragam dari kedalaman polylogarithmic dan ukuran quasipolynomial.