Pseudorandom जनरेटर की अस्तित्व

Question

उसके लिए कैसे दिखाना है $\epsilon>0$, एक फ़ंक्शन मौजूद है $G:\{0,1\}^n->\{0,1\}^{2^{\epsilon n}}$ यह है $2^{\epsilon n}$-प्रणाली, उस स्थिति के बिना जिसमें गणना योग्य है $2^{O(n)}$समय। मैं जो दिखाने की कोशिश कर रहा हूं वह उच्च संभावना के साथ है, अगर हम लेते हैं$\epsilon=1/10$, एक यादृच्छिक $G$इस स्थिति को संतुष्ट करता है। लेकिन यह दिखाने के लिए, हमें दिखाने की जरूरत है, आकार का कोई सर्किट नहीं$<2^{3/10n}$ लंबाई के समान वितरण के बीच अंतर करने में सक्षम हैं $2^{n/10}$ और का उत्पादन $G$। यह मुझे नहीं मिल पा रहा है। क्या कोई मुझे एक दृष्टिकोण दे सकता है?

Answer 1

यदि आप चुनते हैं $G$ पर वर्दी यादृच्छिक वितरण से $\{0, 1\}^n \to \{0, 1\}^{2^{\epsilon n}}$ प्रतिबंध के बिना, फिर कुछ भी (समान रूप से) समान वितरण और उत्पादन के बीच अंतर नहीं कर सकता है $G$, क्योंकि आपने परिभाषा के अनुसार इसे समान रूप से यादृच्छिक बना दिया है। इस बिंदु पर के उत्पादन$G$अब कोई छद्म यादृच्छिक है, यह है यादृच्छिक।