Random self-reducibility
यादृच्छिक आत्म-न्यूनीकरण (आर. एस. आर.) नियम है कि औसत मामले के लिए एक अच्छा एल्गोरिथ्म सबसे खराब मामले के लिए एक अच्छा एल्गोरिथ्म का तात्पर्य है। आर. एस. आर. उदाहरणों के एक बड़े हिस्से को हल करके किसी समस्या के सभी उदाहरणों को हल करने की क्षमता है। परिभाषा यदि किसी फलन f के लिए किसी भी उदाहरण x का मूल्यांकन करने के लिए बहुपद समय में एक या अधिक यादृच्छिक उदाहरणों yi पर f के मूल्यांकन के लिए कम किया जा सकता है, तो यह स्व-कम करने योग्य है (इसे गैर-अनुकूली समान स्व-कटौती के रूप में भी जाना जाता है)। एक यादृच्छिक आत्म-कटौती में, f के क्षेत्र में एक मनमाना सबसे खराब स्थिति उदाहरण x को y1,., yk उदाहरणों के एक यादृच्छिक सेट में मैप किया जाता है। ऐसा इसलिए किया जाता है ताकि f (x) की गणना बहुपद समय में की जा सके, मानचित्रण से सिक्का-उछाल अनुक्रम को देखते हुए, x, और f (y1),., f (yk)। इसलिए, yi पर प्रेरित वितरण के संबंध में औसत लेते हुए, f की औसत-मामले की जटिलता (बहुपद कारकों के भीतर) f की सबसे खराब-मामले की यादृच्छिक जटिलता के समान होती है। ध्यान देने योग्य एक विशेष मामला यह है कि जब प्रत्येक यादृच्छिक उदाहरण yi को f के क्षेत्र में तत्वों के पूरे समूह पर समान रूप से वितरित किया जाता है जिसकी लंबाई |x। होती है। इस मामले में f औसतन उतना ही कठिन है जितना कि यह सबसे खराब स्थिति में है। इस दृष्टिकोण में दो प्रमुख प्रतिबंध हैं। सबसे पहले y1,., yk की पीढ़ी गैर-अनुकूली रूप से की जाती है। इसका मतलब है कि y2 को f (y1) के ज्ञात होने से पहले उठाया जाता है। दूसरा, यह आवश्यक नहीं है कि y1,., yk बिंदुओं को समान रूप से वितरित किया जाए। क्रिप्टोग्राफिक प्रोटोकॉल में अनुप्रयोग ऐसी समस्याएं जिनके लिए डेटा में कुछ गोपनीयता की आवश्यकता होती है (आमतौर पर क्रिप्टोग्राफिक समस्याएं) उस गोपनीयता को सुनिश्चित करने के लिए यादृच्छिककरण का उपयोग कर सकती हैं। वास्तव में, एकमात्र प्रमाणित रूप से सुरक्षित क्रिप्टोग्राफिक प्रणाली (वन-टाइम पैड) की सुरक्षा पूरी तरह से प्रणाली को आपूर्ति किए गए प्रमुख डेटा की यादृच्छिकता पर निर्भर करती है। क्रिप्टोग्राफी का क्षेत्र इस तथ्य का उपयोग करता है कि कुछ संख्या-सैद्धांतिक कार्य यादृच्छिक रूप से आत्म-कम करने योग्य हैं। इसमें संभावित एन्क्रिप्शन और क्रिप्टोग्राफिक रूप से मजबूत स्यूडोरैंडम संख्या पीढ़ी शामिल है। इसके अलावा, उदाहरण-छिपाने वाली योजनाओं (जहां एक कमजोर निजी उपकरण अपने डेटा को प्रकट किए बिना एक मजबूत सार्वजनिक उपकरण का उपयोग करता है) को यादृच्छिक आत्म-कटौती द्वारा आसानी से उदाहरण दिया जाता है। उदाहरण असतत लघुगणक समस्या, द्विघात अवशिष्टता समस्या, आर. एस. ए. व्युत्क्रम समस्या, और एक मैट्रिक्स के स्थायी की गणना करने की समस्या प्रत्येक यादृच्छिक आत्म-कम करने योग्य समस्याएँ हैं। विविक्त लघुगणक प्रमेयः आकार |G। का एक चक्रीय समूह G दिया गया है। यदि एक नियतात्मक बहुपद समय एल्गोरिथ्म ए सभी इनपुट के 1/पॉली (एन) अंश के लिए असतत लघुगणक की गणना करता है (जहां एन = लॉग |G। इनपुट आकार है), तो सभी इनपुट के लिए असतत लघुगणक के लिए एक यादृच्छिक बहुपद समय एल्गोरिथ्म है। एक चक्रीय समूह जी = {जी. आई.। 0 ≤ आई <|G।} के एक जनित्र जी और एक एक्स. जी. को देखते हुए, आधार जी के लिए एक्स का असतत लॉग x = जी. के. के साथ पूर्णांक के (0 ≤ के <|G।) है। B को {0,., |G। −1} पर समान रूप से वितरित करने के लिए लें, फिर xgB = gk + B भी G पर समान रूप से वितरित किया जाता है। इसलिए xgB x से स्वतंत्र है, और इसके लघुगणक की गणना बहुपद समय में प्रायिकता 1/पॉली (n) के साथ की जा सकती है। फिर लॉगजीएक्स ष्ण लॉगजीएक्सजीबी-बी (मॉड |G।) और असतत लघुगणक स्व-कम करने योग्य है। मैट्रिक्स की स्थायी परिभाषा को देखते हुए यह स्पष्ट है कि किसी भी n-by-n मैट्रिक्स M के लिए PERM (M), M में प्रविष्टियों पर डिग्री n का एक बहुभिन्नरूपी बहुपद है। एक मैट्रिक्स की स्थायी गणना करना एक कठिन कम्प्यूटेशनल कार्य है-PERM को #P-पूर्ण (प्रमाण) दिखाया गया है। इसके अलावा, अधिकांश मैट्रिक्स के लिए पी. ई. आर. एम. (एम) की गणना करने की क्षमता का तात्पर्य एक यादृच्छिक कार्यक्रम के अस्तित्व से है जो सभी मैट्रिक्स के लिए पी. ई. आर. एम. (एम) की गणना करता है। यह दर्शाता है कि पी. ई. आर. एम. यादृच्छिक रूप से आत्म-कम करने योग्य है। नीचे दी गई चर्चा उस मामले पर विचार करती है जहाँ मैट्रिक्स प्रविष्टियाँ कुछ अभाज्य p के लिए एक परिमित क्षेत्र Fp से खींची जाती हैं, और जहाँ सभी अंकगणित उस क्षेत्र में किया जाता है। मान लीजिए कि X, Fp से प्रविष्टियों के साथ एक यादृच्छिक n-by-n मैट्रिक्स है। चूँकि किसी भी मैट्रिक्स M + kX की सभी प्रविष्टियाँ k के रैखिक कार्य हैं, उन रैखिक कार्यों को डिग्री n बहुभिन्नरूपी बहुपद के साथ रचना करके जो PERM (M) की गणना करता है, हम k पर एक और डिग्री n बहुपद प्राप्त करते हैं, जिसे हम p (k) कहेंगे। स्पष्ट रूप से, पी (0) एम के स्थायी के बराबर है। मान लीजिए कि हम एक ऐसे प्रोग्राम को जानते हैं जो अधिकांश एन-बाय-एन मैट्रिक्स के लिए पी. ई. आर. एम. (ए) के सही मूल्य की गणना करता है जिसमें एफ. पी.---- विशेष रूप से, उनमें से 1-1/(3एन) की प्रविष्टियां होती हैं। फिर लगभग दो-तिहाई की संभावना के साथ, हम k = 1,2,., n + 1 के लिए PERM (M + kX) की गणना कर सकते हैं। एक बार जब हमारे पास वे n + 1 मान हो जाते हैं, तो हम प्रक्षेप का उपयोग करके p (k) के गुणांक के लिए हल कर सकते हैं (याद रखें कि p (k) में डिग्री n है)। एक बार जब हम p (k) को ठीक से जानते हैं, तो हम p (0) का मूल्यांकन करते हैं, जो PERM (M) के बराबर है। यदि हम ऐसा करते हैं, तो हम एक तिहाई समय गलत होने का जोखिम उठाते हैं, लेकिन कई यादृच्छिक एक्स को चुनकर और उपरोक्त प्रक्रिया को कई बार दोहराकर, और केवल बहुमत विजेता को उत्तर के रूप में प्रदान करके, हम त्रुटि दर को बहुत कम कर सकते हैं। परिणाम यदि एक एन. पी.-पूर्ण समस्या गैर-अनुकूली यादृच्छिक आत्म-कम करने योग्य है तो बहुपद पदानुक्रम σ3 तक गिर जाता है। यदि एक सी. ओ. एन. पी.-कठिन समस्या ओ (लॉग एन/एन) में यादृच्छिक स्व-कम करने योग्य है तो σ2 = Π2। संदर्भ एम. अबादी, जे. फीगेनबाम, और जे. किलियन, ऑन हाइडिंग इन्फॉर्मेशन फ्रॉम एन ओरेकल, जे. कम्पुट। सिस्ट। विज्ञान., 1989 एस. अरोड़ा, अराउंड द पीसीपी थ्योरम, 1996 जे. फीगेनबाम, एल. फोर्टनो, ऑन द रैंडम-सेल्फ-रिड्युसिबिलिटी ऑफ कम्प्लीट सेट्स, 1991 रैंडमाइज्ड एल्गोरिदम