Adleman telah menunjukkan pada tahun 1978 bahwa : jika fungsi boolean dari variabel dapat dihitung dengan rangkaian boolean probabilistik ukuran , maka dapat juga dihitung dengan deterministik sirkuit boolean polinomial ukuran dalam dan ; sebenarnya, dari ukuran . B P P ⊆ P / p o l...
Ketidaksamaan tipe Chernoff digunakan untuk menunjukkan bahwa probabilitas bahwa jumlah variabel acak independen menyimpang secara signifikan dari nilai yang diharapkan secara eksponensial kecil dalam nilai yang diharapkan dan deviasi. Apakah ada ketimpangan tipe Chernoff untuk jumlah variabel acak...
Dengan (iid gaussians dengan rata-rata dan varians ), apakah mungkin (bagaimana?) Untuk mengambil sampel (untuk ) sehingga adalah gaussians berpasangan yang berpasangan dengan mean dan varians .X1,…,XkX1,…,XkX_1,\ldots,X_k1 m = k 2 Y 1 , … , Y m Y i 0 1000111m=k2m=k2m=k^2Y1,…,YmY1,…,YmY_1,...
Algoritma aliran memerlukan pengacakan untuk sebagian besar untuk melakukan apa saja nontrivial, dan karena kendala ruang kecil, perlu PRG yang menggunakan sedikit ruang. Saya tahu dua metode yang telah dikutip untuk digunakan dalam algoritma streaming sejauh ini: kkk -bijaksana PRG independen...
Diketahui bahwa menambahkan pengacakan kesalahan terbatas ke PSPACE tidak menambah daya. Yaitu, BPPSAPCE = PSPACE. Tidak diketahui apakah P = BPP, tetapi diketahui bahwa .B PP⊆ Σ2∩ Π2BPP⊆Σ2∩Π2BPP\subseteq \Sigma_2\cap \Pi_2 Dengan demikian, adalah mungkin (meskipun diduga salah) bahwa menambahkan...
Mengingat komposit jumlah jenderal lapangan saringan terkenal algoritma faktorisasi untuk integer faktorisasi . Ini adalah algoritma acak dan kami mendapatkan kompleksitas yang diharapkan dari faktor . N O ( e √N∈NN∈NN\in\Bbb
Saya sedang membaca makalah berjudul Random Oracles with (out) Programmability . Paragraf terakhir dari bagian 2.3 berbunyi: [Menggunakan pendekatan baru kami] tidak perlu menerapkan teknik derandomisasi asimtotik (dan seragam) klasik yang terkenal berdasarkan lemma Borel-Cantelli . Sejauh...
Saya telah mengembangkan teknik derandomisasi baru yang ditujukan untuk algoritma acak rekursif (atau) algoritma acak yang lebih umum yang menggunakan tumpukan. Sayangnya, saya tidak dapat menemukan algoritma acak alami untuk menerapkan teknik saya. Rantai Markov rekursif dan tata bahasa Stochastic...
Saya punya beberapa pertanyaan tentang menipu sirkuit kedalaman konstan. Ini diketahui bahwa kemerdekaan-bijaksana adalah diperlukan untuk menipu A C 0 sirkuit kedalaman d , di mana n adalah ukuran input. Bagaimana seseorang bisa membuktikan
Saya membaca makalah Impagliazzo dan Wigderson yang terkenal pada tahun 1997. Karena saya baru di bidang ini dan makalah ini adalah versi konferensi singkat, saya mengalami kesulitan mengikuti bukti mereka. Secara khusus, beberapa teorema baru mereka tidak memiliki bukti. Sejauh pengetahuan saya,...
Diberikan sedemikian sehingga koefisien p , q dibatasi oleh B , apakah p ≡ q tahan ?p ( x1, ... , xn) , q( x1, ... , xn) ∈ Z [ x1, ... , xn]p(x1,…,xn),q(x1,…,xn)∈Z[x1,…,xn]p(x_1,\dots,x_n),q(x_1,\dots,x_n)\in \Bbb Z[x_1,\dots,x_n]p,qp,qp,qBBBp≡qp≡qp\equiv q Lemma Schwartz-Zippel berlaku di sini...
Perhitungan dari mesin Turing nondeterministic (NTM) dikenal sebagai pohon konfigurasi, yang berakar pada konfigurasi awal. Setiap transisi dalam program diwakili oleh tautan ayah-anak di pohon ini. Pohon serupa juga dapat dibangun untuk memvisualisasikan perhitungan mesin probabilistik dan...
Inklusi terbalik jelas, karena fakta bahwa setiap bahasa NP yang dapat direduksi sendiri dalam BPP juga dalam RP. Apakah ini juga diketahui berlaku untuk bahasa NP yang tidak dapat direduksi
Biarkan k>0k>0k>0 menjadi konstanta tetap. Diberikan bilangan bulat nnn , kami ingin membangun permutasi σ∈Snσ∈Sn\sigma \in S_n sedemikian rupa sehingga: Konstruksi menggunakan waktu dan ruang konstan (yaitu preprocessing membutuhkan waktu dan ruang konstan). Kita bisa menggunakan...
Dalam pengujian identitas polinomial kami mencari algoritma deterministik untuk menyimpulkan kesetaraan dua polinomial . Melakukan derandomisasi yang dikenal dengan algoritma acak yang efisien dan menghasilkan algoritma deterministik yang efisien adalah masalah terbuka yang penting. Apakah ada...
Tampaknya ada banyak algoritma acak untuk pengujian identitas polinomial, memeriksa apakah polinomial yang diberikan adalah nol. Apakah ada hasil dari algoritma yang melakukan semacam estimasi polinomial pada set poin tertentu? Ini bisa berupa, misalnya, kira-kira sepersekian poin mana dari...
Saya tertarik pada contoh konstruksi dalam teori kompleksitas yang lebih baik daripada konstruksi acak. Satu-satunya contoh konstruksi yang saya tahu adalah di bidang kode koreksi kesalahan. Kode aljabar-geometri lebih baik dalam beberapa rentang parameter daripada kode acak. Orang dapat dengan...
Dengan BPP / linear saya merujuk ke mesin BPP dengan saran linier, yang memenuhi janji ketika diberi saran "benar", dan derandomisasi harus memberi kita, katakanlah, algoritma P / linear atau (SUBEXP / linear). Jika kita menggunakan asumsi yang tidak seragam, saya pikir hasil klasik akan berhasil,...
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 .CC\mathcal{C}BP-...
Pertimbangkan mesin (yaitu, algoritma probabilistik yang menggunakan logspace dan banyak bit acak secara polinomi). Diketahui (Saks-Zhou) bahwa .B PL.BPLBPLB PL ⊆ D SPA CE( L o g1.5( n ) )BPL.⊆DSPSEBUAHCE(lHaig1.5(n))BPL \subseteq DSPACE(log^{1.5}(n)) Pertanyaan saya adalah tentang mesin yang...