Pseudorandom generator untuk automata terbatas

Biarkan menjadi konstanta. Bagaimana kita bisa provably membangun pseudorandom generator yang bodoh -state terbatas automata? $d$ $d$

Di sini, automata terbatas state memiliki node, node mulai, satu set node yang menyatakan status terima, dan dua tepi terarah berlabel 0, 1 yang keluar dari setiap node. Ini mengubah keadaan dengan cara alami saat membaca input. Dengan , temukan sedemikian rupa sehingga untuk setiap state otomat terbatas menghitung beberapa fungsi , $d$ $d$ $\epsilon$ $f:\{0,1\}^{k}\to \{0,1\}^n$ $d$ $A$

| P_{x \sim U_{k}} (A (f (x)) = 1) - P_{x \sim U_{n}} (A (x) = 1) | < ϵ .

$|\mathbb P_{x\sim U_{k}}(A(f(x))=1)-\mathbb P_{x\sim U_n}(A(x)=1)|< \epsilon.$

Di sini menunjukkan distribusi seragam pada variabel , dan kami ingin menjadi sekecil mungkin (misalnya ). Saya sedang berpikir berada di urutan , meskipun kita juga dapat mengajukan pertanyaan secara lebih umum (mis. Apakah jumlah bit yang dibutuhkan akan bertambah dengan ?). $U_k$ $k$ $k$ $\log n$ $d$ $n$ $n$

Beberapa latar belakang

Konstruksi generator pseudorandom penting dalam derandomisasi, tetapi masalah umum (PRG untuk algoritma waktu polinomial) sejauh ini terbukti terlalu sulit. Namun ada kemajuan dalam perhitungan PRG untuk komputasi ruang terbatas. Misalnya makalah terbaru ini ( http://homes.cs.washington.edu/~anuprao/pubs/spaceFeb27.pdf ) memberikan batasan sekitar untuk program percabangan read-once reguler . Pertanyaan dengan program percabangan read-once umum masih terbuka (dengan ), jadi saya bertanya-tanya apakah jawaban untuk penyederhanaan ini diketahui. (Otomat terbatas seperti program percabangan baca-sekali di mana setiap lapisan adalah sama.) $\log n\log d$ $k=\log n$

automata-theory pseudorandomness pseudorandom-generators Holden Lee
sumber

mungkin membantu untuk menjelaskan / menjelaskan beberapa alasan mengapa ini merupakan rumusan alami dari masalah yaitu asal / bkg / perincian / alasan dari ekspresi probabilitas. apakah ada solusi lain yang diketahui dari pertanyaan untuk model lain? apakah itu terkait dengan kerangka kerja PAC dll?

vzn

Saya menambahkan sedikit latar belakang.

Holden Lee

mungkin gagasan set menipu FSM (hal. 12) akan bekerja dengan baik di sini? ("Jika L memiliki perangkat pembodohan tak terbatas, maka L tidak diterima oleh DFA mana pun.")

vzn

Jawaban:

$d$ $n$

$d$ $\subseteq$ $d$ $n$

Manu
sumber

\subseteq

$\subseteq$

$M^n$

bukti yang tampaknya sama ini juga dikutip oleh RJlipton di blog-nya "garansi generator Nisans" . buktinya ternyata berasal dari kertas. Seberapa kuat generator pseudo-acak Nisan? David, Papakonstantinou, Sidiropoulos (2010). juga perhatikan pertanyaan yang lebih dalam & batas yang lebih baik terkait dengan pemisahan kelas kompleksitas utama:

$\mathsf{L} \neq \mathsf{NP}$

vzn
sumber

perhatikan, lihat lebih lanjut, kertas DPS adalah perpanjangan dari kertas Nisans [NIS92] dalam referensi mereka ke mesin yang dibatasi ruang dengan banyak lintasan. ref itu adalah N. Nisan. Generator pseudorandom untuk perhitungan ruang-terbatas. Combinatorica, 12 (4): 449-461, 1992. (juga STOC'90).

vzn

Mungkin jika Anda membaca makalah Nisan, Anda akan melihat bahwa ia menyatakan teorema dalam hal FSM. Juga akan lebih baik jika Anda memberikan batasan kuantitatif

Sasho Nikolov

perhatikan beberapa pernyataan thm dalam hal logspace TMs. lihat juga Model ruang terbatas yang bodoh dan polinomial tingkat rendah yang disurvei , Li, Yang, dt. 1,3 p6 Mesin Ruang Turing yang dapat dibaca dan pernah log

vzn

Baik pertanyaan ini maupun tulisan asli memberikan pernyataan dalam hal FSM. Jadi komentar Anda hampir tidak relevan.

Sasho Nikolov

Bisakah Anda nyatakan teorema yang relevan, dalam formulasi FSM dari makalah Nisan, dalam jawaban Anda? Tidak mencatat yang menyatakannya dengan cara yang berbeda, bukan kertas survei yang menyatakannya dengan cara yang berbeda: pertama menyatakan jawaban aktual untuk pertanyaan aktual ? Adakah yang sulit dipahami mengapa hal itu baik dilakukan?

Sasho Nikolov