Ini adalah pertanyaan penelitian yang indah dengan beberapa aspek untuk itu, dan ada berbagai cara untuk memformalisasikan pertanyaan tergantung pada apakah dengan ekstraktor maksud Anda ekstraktor unggulan atau ekstraktor tanpa biji dan apakah dengan PRG maksud Anda PRG untuk sirkuit Boolean atau keluarga yang lebih khusus (misalnya , ruang bias epsilon). Berikut ini beberapa pemikiran tidak resmi dari kepala saya (tetapi bukan jawaban lengkap):
Untuk ekstraktor unggulan vs PRG kotak hitam (seperti dalam Nisan-Wigderson), tampaknya PRG kotak hitam adalah objek yang lebih kuat daripada ekstraktor. Jika Anda melihat ekstraktor Trevisan, itu bukan hanya ekstraktor yang dapat dihitung waktu polinomialnya tetapi juga memiliki sifat tambahan yang penting. Yaitu, analisis memiliki elemen komputasi lokal dan efisien di dalamnya (yaitu, algoritma daftar-decoding lokal). Fitur tambahan ini tidak begitu penting untuk extractor (sebagai objek kombinatorial, bahkan jika kita memerlukan extractor untuk dihitung waktu-polinomial) tetapi sangat penting untuk PRG (sehingga alat pemecah dapat secara efisien diubah menjadi sebuah algoritma untuk menghitung fungsi keras). Bahkan ini dapat diformalkan, dan Ta-Shma dan Zuckerman telah memformalkan definisi "kotak-hitam PRG" dalam makalah mereka "Kode Extractor". Mereka menunjukkan bahwa PRG kotak hitam dapat digunakan untuk membuat ekstraktor. Untuk kebalikannya, saya pikir orang dapat menunjukkan bahwa setiap ekstraktor yang memenuhi properti di atas sesuai dengan PRG kotak hitam (dalam bahasa extractor, ini berarti bahwa kode extractor yang dihasilkan harus memiliki daftar-decoder-keputusan lunak yang efisien). Anda juga dapat menemukan makalah Vadhan "The Unified Theory of Pseudorandomness" yang relevan dengan diskusi ini.
Dalam dunia ekstraktor tanpa biji, Trevisan dan Vadhan menunjukkan bahwa fungsi keras untuk keluarga sirkuit tertentu menghasilkan ekstraktor untuk keluarga tersebut (kertas "Extractors for Samplable Sources"). Jadi, misalnya fungsi yang sangat keras rata-rata untuk AC0 dapat mengekstraksi dari sumber sampel oleh sirkuit AC0 (jika min-entropi sumber cukup besar). Fungsi keras secara alami berhubungan dengan PRG (seperti yang diamati oleh Nisan-Wigderson). Jadi di sini kita kembali mendapatkan interaksi yang agak berbeda antara PRG dan ekstraktor tanpa biji. Namun kurang jelas bagaimana seseorang dapat menggunakan ekstraktor untuk sumber yang dapat disampel (mungkin memuaskan beberapa sifat tambahan) untuk mendapatkan PRG (titik peluru berikutnya memberikan jawaban parsial untuk ini). Arah ini mungkin kurang menarik daripada diskusi di atas untuk ekstraktor unggulan karena sampai saat ini kami tidak
Dari sudut pandang kombinatorial, ada kesamaan antara PRG dan ekstraktor. Kita dapat melihat PRG sebagai himpunan dari poin dalam (hasil dari PRG untuk semua benih yang mungkin) atau setara, pewarnaan dari dimensi hypercube dalam dua warna. Demikian pula, ekstraktor dengan satu bit output (atau fungsi Boolean, dalam hal ini) dapat dilihat sebagai satu set poin (yang mana ekstraktor mengevaluasi ) atau pewarnaan (secara umum, jumlah warna akan menjadi mana adalah panjang output). Sekarang, PRG dengan set titik menipu fungsi dengan titik set iffdekat dengan{ 0 , 1 } n n 0 2 m m S F | S ∩ F | / | S | | F | / 2 n F S | S ∩ F | / | S | 1 / 2 { 0 , 1 } n n - 1 1 S 0 n - 1S{ 0 , 1 }nn02mmSF| S∩ F| / | S|| F| / 2n . Juga, ekstraktor dengan titik set ekstrak dari sumber datar yang terdistribusi secara seragam pada set poin iffdekat dengan . Kesamaan antara definisi ini memungkinkan seseorang untuk menyimpulkan beberapa kesimpulan yang bermakna. Misalnya, lihat ekstraktor afin di atas yang mengekstrak dari min-entropi , dan menghasilkan bit. Sekarang perhatikan set dari string yang dipetakan ke, katakanlah, oleh extractor dan menerjemahkannya seperti di atas ke "PRG" (dengan panjang bijiFS| S∩ F| / | S|1 / 2{ 0 , 1 }nn - 11S0n - 1). Sekarang interpretasi pewarnaan di atas menunjukkan bahwa fungsi yang dihasilkan memang PRG untuk fungsi linier; yaitu, kita mendapatkan generator yang bias epsilon dari ekstraktor. Ini adalah hubungan yang bermakna tetapi mungkin tidak begitu berguna karena PRG yang dihasilkan meregangkan benih hanya dengan satu bit. Mungkin hasil yang lebih baik dapat disimpulkan jika extractor mengeluarkan lebih banyak bit, tetapi saya belum memeriksanya dengan seksama.
Salil Vadhan menulis kepada saya bahwa jawaban atas pertanyaan saya diketahui, dan PRGs setara dengan ekstraktor.
Mengutipnya:
"Lihat Proposisi 21 dan diskusi yang mengikutinya dalam survei saya http://people.seas.harvard.edu/~salil/research/unified-icm.pdf (Ada kesalahan ketik -" kotak hitam penguat kekerasan "harus" hitam " -konstruksi PRG kotak ")
Dikatakan ekstraktor setara dengan konstruksi PRG kotak hitam di mana Anda hanya peduli tentang jumlah saran, dan bukan waktu berjalan, dalam pengurangan. Meminta waktu berjalan terbatas berarti meminta ekstraktor dengan "decoding daftar lokal". "
sumber
Ada kertas bagus dari Chris Umans mengenai analogi pertanyaan ini untuk para pendispersi: http://www.cs.caltech.edu/~umans/papers/U05-final.pdf
Dia menunjukkan bahwa disperser yang memiliki prosedur rekonstruksi polinomial-waktu, tetapi tidak harus properti decoding lokal, menyiratkan keberadaan memukul generator set.
Berikut ini cara lain untuk melihatnya: Extractor dapat dilihat sebagai kode yang dapat dipulihkan daftar (yang merupakan varian yang lebih kuat dari kode yang dapat didekodekan), dan PRG kotak hitam dapat dilihat dari kode lokal yang dapat dipulihkan. Disperser dapat dilihat sebagai kode yang dapat dipulihkan daftar untuk kesalahan nol. Apa yang ditunjukkan Chris adalah bahwa kode yang dapat dipulihkan daftar untuk kesalahan nol yang memiliki prosedur pemulihan daftar waktu polinomial menyiratkan adanya kode yang dapat dipulihkan dengan prosedur pemulihan daftar lokal .
sumber