यादृच्छिक एल्गोरिथ्म

"यादृच्छिक एल्गोरिदम" redirects here. Not to be confused with एल्गोरिथम यादृच्छिकता.

यादृच्छिक एल्गोरिदम एक एल्गोरिदम है जो अपने तर्क या प्रक्रिया के हिस्से के रूप में यादृच्छिकता की डिग्री को नियोजित करता है। एल्गोरिथ्म आम तौर पर यादृच्छिक बिट्स द्वारा निर्धारित यादृच्छिक के सभी संभावित विकल्पों पर "औसत मामले" में अच्छा प्रदर्शन प्राप्त करने की आशा में, अपने व्यवहार को निर्देशित करने के लिए सहायक निविष्ट के रूप में एक समान यादृच्छिक (असतत) बिट्स का उपयोग करता है; इस प्रकार या तो चलने का समय, या प्रक्षेपण (या दोनों) यादृच्छिक चर हैं।

किसी को यादृच्छिक निविष्ट का उपयोग करने वाले एल्गोरिदम के बीच अंतर करना होगा ताकि वे हमेशा सही उत्तर के साथ समाप्त हो जाएं, लेकिन जहां अपेक्षित चलने का समय सीमित है (लास वेगास कलन विधि, उदाहरण के लिए क्विक सॉर्ट), और एल्गोरिदम जिनके पास गलत परिणाम उत्पन्न करने का मौका है (मोंटे कार्लो एल्गोरिथ्म, उदाहरण के लिए न्यूनतम फीडबैक आर्क सेट समस्या के लिए मोंटे कार्लो एल्गोरिदम) या तो विफलता का संकेत देकर या समाप्त करने में विफल होने पर परिणाम उत्पन्न करने में विफल हैं। कुछ मामलों में, समस्या को हल करने का एकमात्र व्यावहारिक साधन संभाव्य एल्गोरिदम हैं।

सामान्य अभ्यास में, यादृच्छिक बिट्स के सच्चे स्रोत के स्थान पर छद्म यादृच्छिक संख्या जनरेटर का उपयोग करके यादृच्छिक एल्गोरिदम का अनुमान लगाया जाता है; ऐसा कार्यान्वयन अपेक्षित सैद्धांतिक व्यवहार और गणितीय गारंटी से विचलित हो सकता है जो एक आदर्श वास्तविक यादृच्छिक संख्या जनरेटर के अस्तित्व पर निर्भर हो सकता है।

प्रेरणा

प्रेरक उदाहरण के रूप में, n तत्वों की सरणी डेटा संरचना में 'a' निष्कर्ष की समस्या पर विचार करें।

निविष्ट: n≥2 तत्वों की सरणी, जिसमें आधे a हैं और अन्य आधे b हैं।

प्रक्षेपण: सरणी में a खोजें।

हम एल्गोरिथ्म के दो संस्करण देते हैं, एक लास वेगास एल्गोरिथम और एक मोंटे कार्लो एल्गोरिथम।

लास वेगास एल्गोरिथम:

findingA_LV(array A, n)
begin
    repeat
        Randomly select one element out of n elements.
    until 'a' is found
end

यह एल्गोरिथ्म प्रायिकता 1 के साथ सफल होता है। पुनरावृत्तियों की संख्या भिन्न होती है और अक्रमतः बड़ी हो सकती है, लेकिन पुनरावृत्तियों की अपेक्षित संख्या है

$\lim _{n\to \infty }\sum _{i=1}^{n}{\frac {i}{2^{i}}}=2$

चूंकि यह स्थिर है, कई कॉलों पर अपेक्षित रन टाइम है $\Theta (1)$. (बिग थीटा नोटेशन देखें)

मोंटे कार्लो एल्गोरिथम:

findingA_MC(array A, n, k)
begin
    i := 0
    repeat
        Randomly select one element out of n elements.
        i := i + 1
    until i = k or 'a' is found
end

यदि 'a' पाया जाता है, तो एल्गोरिथम सफल होता है, अन्यथा एल्गोरिथम विफल हो जाता है। k पुनरावृत्तियों के बाद, 'a' निष्कर्ष की संभावना है:

$\Pr[\mathrm {find~a} ]=1-(1/2)^{k}$

यह एल्गोरिदम सफलता की गारंटी नहीं देता है, लेकिन रन टाइम सीमित है। पुनरावृत्तियों की संख्या हमेशा k से कम या उसके बराबर होती है। k को स्थिर रखने के लिए रन टाइम (अपेक्षित और पूर्ण) $\Theta (1)$ है

यादृच्छिक एल्गोरिदम विशेष रूप से उपयोगी होते हैं जब दुर्भावनापूर्ण विपक्षी या आक्रामक का सामना करना पड़ता है जो जानबूझकर एल्गोरिदम को खराब निविष्ट देने की कोशिश करता है (देखें वर्स्ट-केस कम्प्लेक्सिटी और प्रतिस्पर्धी विश्लेषण (ऑनलाइन एल्गोरिदम)) जैसे बंदी की दुविधा में है। यही कारण है कि क्रिप्टोग्राफी में यादृच्छिकता सर्वव्यापी है। क्रिप्टोग्राफ़िक अनुप्रयोगों में, छद्म-यादृच्छिक संख्याओं का उपयोग नहीं किया जा सकता है, क्योंकि विरोधी उन्हें पूर्वानुमान कर सकते हैं, एल्गोरिदम प्रभावी रूप से निर्धारक बनाते हैं। इसलिए, या तो वास्तव में यादृच्छिक संख्याओं का स्रोत या क्रिप्टोग्राफ़िक रूप से सुरक्षित छद्म-यादृच्छिक संख्या जनरेटर की आवश्यकता होती है। अन्य क्षेत्र जिसमें यादृच्छिकता निहित है, क्वांटम कम्प्यूटिंग है।

उपरोक्त उदाहरण में, लास वेगास एल्गोरिथम हमेशा सही उत्तर देता है, लेकिन इसका चलने का समय यादृच्छिक चर है। मोंटे कार्लो एल्गोरिथम (सिमुलेशन के लिए मोंटे कार्लो विधि से संबंधित) को उस समय की मात्रा में पूरा करने की गारंटी दी जाती है जिसे फ़ंक्शन द्वारा निविष्ट आकार और उसके पैरामीटर k द्वारा बाध्य किया जा सकता है, लेकिन त्रुटि की छोटी संभावना की अनुमति देता है। ध्यान दें कि किसी भी लास वेगास एल्गोरिथम को मोंटे कार्लो एल्गोरिथम (मार्कोव की असमानता के माध्यम से) में परिवर्तित किया जा सकता है, यदि यह निर्दिष्ट समय के भीतर पूरा करने में विफल रहता है, तो यह यादृच्छिक, संभवतः गलत उत्तर देता है। इसके विपरीत, यदि कोई उत्तर सही है या नहीं, यह जांचने के लिए कुशल सत्यापन प्रक्रिया मौजूद है, तो मोंटे कार्लो एल्गोरिथम को सही उत्तर प्राप्त होने तक मोंटे कार्लो एल्गोरिथम को बार-बार चलाकर लास वेगास एल्गोरिथम में परिवर्तित किया जा सकता है।

कम्प्यूटेशनल जटिलता

कम्प्यूटेशनल जटिलता सिद्धांत मॉडल यादृच्छिक एल्गोरिदम को संभाव्य ट्यूरिंग मशीन के रूप में लास वेगास एल्गोरिथ्म और मोंटे कार्लो एल्गोरिदम दोनों पर विचार किया जाता है, और कई जटिलता वर्ग का अध्ययन किया जाता है। सबसे बुनियादी यादृच्छिक जटिलता वर्ग आरपी (जटिलता) है, जो निर्णय समस्याओं का वर्ग है जिसके लिए कुशल (बहुपद समय) यादृच्छिक एल्गोरिदम (या संभाव्य ट्यूरिंग मशीन) है जो पूर्ण निश्चितता के साथ नहीं- उदाहरण को पहचानता है और हाँ-उदाहरण को पहचानता है कम से कम 1/2 की संभावना के साथ है। RP के लिए पूरक वर्ग co-RP है। बहुपद समय औसत केस रनिंग टाइम वाले एल्गोरिदम (संभवतः गैर-समापन) वाले समस्या वर्ग जिनके प्रक्षेपण हमेशा सही होते हैं उन्हें ज़ेडपीपी (जटिलता) में कहा जाता है।

समस्याओं का वह वर्ग जिसके लिए हाँ और नहीं दोनों उदाहरणों को कुछ त्रुटि के साथ पहचानने की अनुमति दी जाती है, परिबद्ध-त्रुटि संभाव्य बहुपद कहलाती है। यह वर्ग P (जटिलता) के यादृच्छिक समतुल्य के रूप में कार्य करता है, अर्थात बीपीपी कुशल यादृच्छिक एल्गोरिदम के वर्ग का प्रतिनिधित्व करता है।

प्रारंभिक इतिहास

सॉर्टिंग

क्विक सॉर्ट की खोज 1959 में टोनी होरे द्वारा की गई थी, और बाद में 1961 में प्रकाशित हुई थी। उसी वर्ष, होरे ने त्वरित चयन एल्गोरिथ्म प्रकाशित किया, जो रैखिक अपेक्षित समय में किसी सूची का मध्य तत्व पाता है। यह 1973 तक खुला रहा कि क्या नियतात्मक रैखिक-समय एल्गोरिथम मौजूद है।

संख्या सिद्धांत

1917 में, हेनरी कैबॉर्न पॉकलिंगटन ने यादृच्छिक एल्गोरिथम पेश किया, जिसे पॉकलिंगटन के एल्गोरिथ्म के रूप में जाना जाता है, जो कुशलतापूर्वक वर्गमूल मॉड्यूलो अभाज्य संख्या को निष्कर्ष के लिए है।1970 में, एल्विन बर्लेकैंप ने परिमित क्षेत्र पर बहुपद की वर्गमूल की कुशलता से गणना करने के लिए यादृच्छिक एल्गोरिथ्म पेश किया है। 1977 में, रॉबर्ट एम. सोलोवे और वोल्कर स्ट्रास ने बहुपद-समय सोलोवे-स्ट्रैसन प्रारंभिक परीक्षण की खोज की थी (अर्थात, किसी संख्या की प्रारंभिक परीक्षा का निर्धारण)। इसके तुरंत बाद माइकल ओ. राबिन ने प्रदर्शित किया कि 1976 मिलर के प्रारंभिक परीक्षण को बहुपद-समय यादृच्छिक एल्गोरिथम में भी बदला जा सकता है। उस समय, प्रारंभिक परीक्षण के लिए कोई सिद्ध बहुपद-समय नियतात्मक एल्गोरिथम ज्ञात नहीं था।

डेटा संरचनाएं

जल्द से जल्द यादृच्छिक डेटा संरचनाओं में से हैश तालिका है, जिसे 1953 में आईबीएम में हंस पीटर लुहान द्वारा पेश किया गया था। लुहान की हैश टेबल ने संघट्ट को हल करने के लिए चेनिंग का इस्तेमाल किया और लिंक्ड सूची के पहले अनुप्रयोगों में से एक था।इसके बाद, 1954 में, आईबीएम रिसर्च के जीन अमदहल, ऐलेन एम. मैकग्रा, नथानिएल रोचेस्टर (कंप्यूटर वैज्ञानिक), और आर्थर सैमुअल (कंप्यूटर वैज्ञानिक) ने रैखिक जांच शुरू की,हालांकि 1957 में स्वतंत्र रूप से एंड्री एर्शोव का भी यही विचार था।1962 में, डोनाल्ड नुथ ने रेखीय जांच का पहला सही विश्लेषण किया,हालाँकि उनके विश्लेषण वाला ज्ञापन बहुत बाद तक प्रकाशित नहीं हुआ था। पहला प्रकाशित विश्लेषण 1966 में कोनहेम और वीस के कारण हुआ था।

हैश टेबल पर प्रारंभिक कार्य या तो पूरी तरह यादृच्छिक हैश फ़ंक्शन तक पहुंच मानते हैं या मानते हैं कि कीज़ स्वयं यादृच्छिक थीं।1979 में, कार्टर और वेगमैन ने यूनिवर्सल हैशिंग की शुरुआत की, जो उन्होंने दिखाया कि प्रति ऑपरेशन निरंतर अपेक्षित समय के साथ चेन हैश टेबल को लागू करने के लिए इस्तेमाल किया जा सकता है।

यादृच्छिक डेटा संरचनाओं पर प्रारंभिक कार्य भी हैश टेबल से आगे बढ़ता है। 1970 में, बर्टन हावर्ड ब्लूम ने अनुमानित-सदस्यता डेटा संरचना पेश की जिसे ब्लूम फिल्टर के रूप में जाना जाता है। 1989 में, रायमुंड सीडेल और सेसिलिया आर. आरागॉन ने यादृच्छिक संतुलित खोज तरु पेश किया जिसे ट्रीप के रूप में जाना जाता है। उसी वर्ष, विलियम पुघ (कंप्यूटर वैज्ञानिक) ने एक और यादृच्छिक खोज तरु पेश किया जिसे स्किप सूची के रूप में जाना जाता है।

कॉम्बिनेटरिक्स में अंतर्निहित उपयोग

कंप्यूटर विज्ञान में यादृच्छिक एल्गोरिदम के लोकप्रिय होने से पहले, पॉल एर्डोस ने गणितीय वस्तुओं के अस्तित्व को स्थापित करने के लिए गणितीय तकनीक के रूप में यादृच्छिक निर्माण के उपयोग को लोकप्रिय बनाया था। इस तकनीक को संभाव्य विधि के रूप में जाना जाने लगा। पॉल एर्दोस ने 1947 में संभाव्यता पद्धति का अपना पहला आवेदन दिया, जब उन्होंने रैमसे ग्राफ के अस्तित्व को स्थापित करने के लिए सरल यादृच्छिक निर्माण का उपयोग किया था। उन्होंने 1959 में उच्च परिधि और रंगीन संख्या वाले ग्राफ के अस्तित्व को स्थापित करने के लिए प्रसिद्ध रूप से अधिक परिष्कृत यादृच्छिक एल्गोरिथ्म का उपयोग किया था।

उदाहरण

क्विकसॉर्ट

क्विकसॉर्ट एक परिचित, आमतौर पर इस्तेमाल किया जाने वाला एल्गोरिदम है जिसमें यादृच्छिकता उपयोगी हो सकती है। इस एल्गोरिथम के कई नियतात्मक संस्करणों के लिए O(n²) की आवश्यकता होती है कुछ अच्छी तरह से परिभाषित निविष्ट वर्ग (जैसे कि पहले से ही क्रमबद्ध सरणी) के लिए n संख्याओं को सॉर्ट करने का समय, निविष्ट के विशिष्ट वर्ग के साथ जो पिवट चयन के लिए प्रोटोकॉल द्वारा परिभाषित इस व्यवहार को उत्पन्न करता है। हालांकि, अगर एल्गोरिद्म पिवट तत्वों को यादृच्छिक रूप से समान रूप से चुनता है, तो निविष्ट की विशेषताओं की परवाह किए बिना O(n log n) समय में समाप्त होने की संभावना काफी अधिक होती है।

ज्यामिति में यादृच्छिक वृद्धिशील निर्माण

कम्प्यूटेशनल ज्यामिति में, उत्तल हल या डेलाउने त्रिभुज जैसी संरचना बनाने के लिए मानक तकनीक निविष्ट बिंदुओं को यादृच्छिक रूप से क्रमबद्ध करना है और फिर उन्हें मौजूदा संरचना में एक-एक करके सम्मिलित करना है। यादृच्छिककरण यह सुनिश्चित करता है कि सम्मिलन के कारण संरचना में परिवर्तनों की अपेक्षित संख्या कम है, और इसलिए एल्गोरिथम के अपेक्षित चलने का समय ऊपर से बाध्य किया जा सकता है। इस तकनीक को यादृच्छिक वृद्धिशील निर्माण के रूप में जाना जाता है।

न्यूनतम कट

Main article: कार्गर का एल्गोरिदम

निविष्ट: ग्राफ सिद्धांत G(V,E)

प्रक्षेपण: कट (ग्राफ सिद्धांत) L और R में कोने को विभाजित करता है, जिसमें L और R के बीच किनारों की न्यूनतम संख्या होती है।

याद रखें कि एक (बहु-) ग्राफ़ में दो नोड्स, यू और वी के किनारे का संकुचन, किनारों के साथ एक नया नोड यू देता है, जो दोनों किनारों पर घटना के किनारों का मिलन है। यू और वी को जोड़ने वाले किसी भी किनारे को छोड़कर यू या वी। चित्र 1 वर्टेक्स ए और बी के संकुचन का एक उदाहरण देता है। संकुचन के बाद, परिणामी ग्राफ़ में समानांतर किनार हो सकते हैं, लेकिन इसमें कोई सेल्फ लूप नहीं होता है। फ़ाइल: कार्गर का एकल रन 's Mincut algorithm.svg|thumb|340px|चित्र 2: 10-शीर्ष ग्राफ़ पर कार्गर के एल्गोरिथम का सफल संचालन। न्यूनतम कट का आकार 3 है और इसे शीर्ष रंगों द्वारा दर्शाया गया है।

चित्र 1: शीर्ष A और B का संकुचन

कार्गर का बुनियादी एल्गोरिथ्म:

शुरू
    मैं = 1
    दोहराना
        दोहराना
            जी में एक यादृच्छिक किनारा (यू, वी) ∈ ई लें
            u और v को संकुचन u' से बदलें
        जब तक केवल 2 नोड शेष रहें
        संबंधित कट परिणाम सी प्राप्त करेंi

मैं = मैं + 1

    जब तक मैं = एम
    सी के बीच न्यूनतम कटौती का उत्पादन करें1, सी2, ..., सीm.
अंत

बाहरी लूप के प्रत्येक निष्पादन में, एल्गोरिथ्म आंतरिक लूप को तब तक दोहराता है जब तक कि केवल 2 नोड शेष न रह जाएं, संबंधित कट प्राप्त हो जाता है। एक निष्पादन का रन टाइम है $O(n)$, और n शीर्षों की संख्या को दर्शाता है। बाहरी लूप के m बार निष्पादन के बाद, हम सभी परिणामों के बीच न्यूनतम कट का उत्पादन करते हैं। चित्र 2 एक देता है एल्गोरिथ्म के एक निष्पादन का उदाहरण। निष्पादन के बाद, हमें आकार 3 में कटौती मिलती है।

Lemma 1 — Let k be the min cut size, and let C = {e₁, e₂, ..., e_k} be the min cut. If, during iteration i, no edge e ∈ C is selected for contraction, then C_i = C.

Proof

If G is not connected, then G can be partitioned into L and R without any edge between them. So the min cut in a disconnected graph is 0. Now, assume G is connected. Let V=L∪R be the partition of V induced by C : C = { {u,v} ∈ E : u ∈ L,v ∈ R} (well-defined since G is connected). Consider an edge {u,v} of C. Initially, u,v are distinct vertices. As long as we pick an edge $f\neq e$, u and v do not get merged. Thus, at the end of the algorithm, we have two compound nodes covering the entire graph, one consisting of the vertices of L and the other consisting of the vertices of R. As in figure 2, the size of min cut is 1, and C = {(A,B)}. If we don't select (A,B) for contraction, we can get the min cut.

Lemma 2 — If G is a multigraph with p vertices and whose min cut has size k, then G has at least pk/2 edges.

Proof

Because the min cut is k, every vertex v must satisfy degree(v) ≥ k. Therefore, the sum of the degree is at least pk. But it is well known that the sum of vertex degrees equals 2|E|. The lemma follows.

एल्गोरिदम का विश्लेषण

एल्गोरिद्म के सफल होने की प्रायिकता 1 − संभावना है कि सभी प्रयास विफल हो जाते हैं। स्वतंत्रता से, सभी प्रयासों के विफल होने की प्रायिकता है

$$\prod _{i=1}^{m}\Pr(C_{i}\neq C)=\prod _{i=1}^{m}(1-\Pr(C_{i}=C)).$$

लेम्मा 1 द्वारा, संभावना है कि C_i = C संभावना है कि पुनरावृत्ति i के दौरान C का कोई किनारा नहीं चुना गया है। आंतरिक पाश पर विचार करें और जाने दें G_j j किनारे के संकुचन के बाद ग्राफ़ को निरूपित करें, जहाँ j ∈ {0, 1, …, n − 3}. G_j है n − j शिखर। हम सशर्त संभाव्यता के श्रृंखला नियम का उपयोग करते हैं। संभावना है कि पुनरावृत्ति j पर चुना गया किनारा C में नहीं है, यह देखते हुए कि C का कोई किनारा पहले नहीं चुना गया है $1-{\frac {k}{|E(G_{j})|}}$. ध्यान दें कि G_j अभी भी आकार k का न्यूनतम कट है, इसलिए लेम्मा 2 के अनुसार, यह अभी भी कम से कम है ${\frac {(n-j)k}{2}}$ किनारों।

इस प्रकार, $1-{\frac {k}{|E(G_{j})|}}\geq 1-{\frac {2}{n-j}}={\frac {n-j-2}{n-j}}$.

तो चेन नियम से, न्यूनतम कट सी निष्कर्ष की संभावना है

$$\Pr[C_{i}=C]\geq \left({\frac {n-2}{n}}\right)\left({\frac {n-3}{n-1}}\right)\left({\frac {n-4}{n-2}}\right)\ldots \left({\frac {3}{5}}\right)\left({\frac {2}{4}}\right)\left({\frac {1}{3}}\right).$$

निरस्तीकरण देता है $\Pr[C_{i}=C]\geq {\frac {2}{n(n-1)}}$. इस प्रकार एल्गोरिथ्म के सफल होने की संभावना कम से कम है $1-\left(1-{\frac {2}{n(n-1)}}\right)^{m}$. के लिए $m={\frac {n(n-1)}{2}}\ln n$, यह इसके बराबर है $1-{\frac {1}{n}}$. एल्गोरिथ्म संभाव्यता के साथ न्यूनतम कटौती पाता है $1-{\frac {1}{n}}$, समय के भीतर $O(mn)=O(n^{3}\log n)$.

डेरेंडोमाइजेशन

यादृच्छिकता को अंतरिक्ष और समय जैसे संसाधन के रूप में देखा जा सकता है। Derandomization तब यादृच्छिकता को हटाने की प्रक्रिया है (या जितना संभव हो उतना कम उपयोग करना)। यह वर्तमान में ज्ञात नहीं है कि क्या सभी एल्गोरिदम को उनके चलने के समय में उल्लेखनीय वृद्धि किए बिना डीरैंडमाइज किया जा सकता है। उदाहरण के लिए, एल्गोरिदम के विश्लेषण में, यह अज्ञात है कि क्या पी (जटिलता) = परिबद्ध-त्रुटि संभाव्य बहुपद, यानी, हम नहीं जानते कि क्या हम एक यादृच्छिक यादृच्छिक एल्गोरिदम ले सकते हैं जो एक छोटी त्रुटि संभावना के साथ बहुपद समय में चलता है और इसे डीरैंडमाइज करता है। यादृच्छिकता का उपयोग किए बिना बहुपद समय में चलाने के लिए।

ऐसे विशिष्ट तरीके हैं जिन्हें विशेष यादृच्छिक एल्गोरिदम को यादृच्छिक बनाने के लिए नियोजित किया जा सकता है:

• सशर्त संभावनाओं की विधि, और इसका सामान्यीकरण, निराशावादी अनुमानक
• विसंगति सिद्धांत (जिसका उपयोग ज्यामितीय एल्गोरिदम को अलग करने के लिए किया जाता है)
• एल्गोरिथ्म द्वारा उपयोग किए जाने वाले यादृच्छिक चर में सीमित स्वतंत्रता का शोषण, जैसे कि सार्वभौमिक हैशिंग में उपयोग की जाने वाली जोड़ीदार स्वतंत्रता
• प्रारंभिक यादृच्छिकता की सीमित मात्रा को बढ़ाने के लिए विस्तारक ग्राफ (या सामान्य रूप से फैलाने वाले) का उपयोग (यह अंतिम दृष्टिकोण एक यादृच्छिक स्रोत से छद्म यादृच्छिक बिट्स उत्पन्न करने के रूप में भी जाना जाता है, और छद्म यादृच्छिकता के संबंधित विषय की ओर जाता है)
• एल्गोरिथम के कार्यों के लिए यादृच्छिकता के स्रोत के रूप में हैश फंकशन का उपयोग करने के लिए यादृच्छिक एल्गोरिथ्म को बदलना, और फिर हैश फ़ंक्शन के सभी संभावित मापदंडों (बीजों) को क्रूर-बल खोज | ब्रूट-फोर्सिंग द्वारा एल्गोरिथ्म को अलग करना। इस तकनीक का प्रयोग आम तौर पर नमूना स्थान को व्यापक रूप से निष्कर्ष और एल्गोरिदम को नियतात्मक बनाने के लिए किया जाता है (उदाहरण के लिए यादृच्छिक ग्राफ एल्गोरिदम)

जहां यादृच्छिकता मदद करती है

जब संगणना का मॉडल ट्यूरिंग मशीनों तक ही सीमित है, तो यह वर्तमान में एक खुला प्रश्न है कि क्या यादृच्छिक विकल्प बनाने की क्षमता बहुपद समय में कुछ समस्याओं को हल करने की अनुमति देती है जिसे इस क्षमता के बिना बहुपद समय में हल नहीं किया जा सकता है; यह सवाल है कि क्या पी = बीपीपी। हालाँकि, अन्य संदर्भों में, समस्याओं के विशिष्ट उदाहरण हैं जहाँ यादृच्छिककरण से सख्त सुधार होते हैं।

• प्रारंभिक प्रेरक उदाहरण के आधार पर: 2 की एक घातीय रूप से लंबी स्ट्रिंग दी गई है^k वर्ण, आधा a और आधा b, एक रैंडम-एक्सेस मशीन के लिए 2 की आवश्यकता होती है^k−1 a की अनुक्रमणिका निष्कर्ष के लिए सबसे खराब स्थिति में खोजता है; अगर इसे यादृच्छिक विकल्प बनाने की अनुमति है, तो यह लुकअप की अपेक्षित बहुपद संख्या में इस समस्या को हल कर सकता है।
• अंतः स्थापित प्रणालियाँ या साइबर-भौतिक प्रणाली में एक संख्यात्मक गणना करने का प्राकृतिक तरीका एक परिणाम प्रदान करना है जो उच्च संभावना (या संभवतः लगभग सही गणना (PACC)) के साथ सही परिणाम का अनुमान लगाता है। अनुमानित और सही संगणना के बीच विसंगति हानि के मूल्यांकन से जुड़ी कठिन समस्या को यादृच्छिककरण का सहारा लेकर प्रभावी ढंग से संबोधित किया जा सकता है
• संचार जटिलता में, दो तारों की समानता का उपयोग करके कुछ विश्वसनीयता के लिए सत्यापित किया जा सकता है $\log n$ एक यादृच्छिक प्रोटोकॉल के साथ संचार के बिट्स। किसी भी नियतात्मक प्रोटोकॉल की आवश्यकता होती है $\Theta (n)$ बिट्स अगर एक मजबूत प्रतिद्वंद्वी के खिलाफ बचाव करते हैं।
• बहुपद समय में अक्रमतः परिशुद्धता के लिए एक उत्तल शरीर की मात्रा का अनुमान एक यादृच्छिक एल्गोरिदम द्वारा लगाया जा सकता है। इमरे बैरनी | बैरनी और ज़ोलटन फ़्यूरेडी | फ़्यूरेडी ने दिखाया कि कोई नियतात्मक एल्गोरिथम ऐसा नहीं कर सकता है। यह बिना शर्त के सच है, यानी किसी भी जटिलता-सैद्धांतिक मान्यताओं पर भरोसा किए बिना, उत्तल शरीर को केवल एक ब्लैक बॉक्स के रूप में माना जा सकता है।
• एक जगह का अधिक जटिलता-सैद्धांतिक उदाहरण जहां यादृच्छिकता मदद करने के लिए प्रकट होती है वह वर्ग आईपी (जटिलता) है। IP में वे सभी भाषाएँ शामिल हैं जिन्हें (उच्च संभावना के साथ) एक सर्व-शक्तिशाली प्रोवर और एक सत्यापनकर्ता के बीच बहुपद रूप से लंबी बातचीत द्वारा स्वीकार किया जा सकता है जोबीपीपी एल्गोरिथम को लागू करता है। आईपी ​​\u003d पीएसपीएसीई। हालाँकि, यदि यह आवश्यक है कि सत्यापनकर्ता नियतात्मक हो, तो IP = NP (जटिलता)।
• एक रासायनिक प्रतिक्रिया नेटवर्क में (ए + बी → 2 सी + डी जैसी प्रतिक्रियाओं का एक सीमित सेट अणुओं की एक सीमित संख्या पर काम कर रहा है), प्रारंभिक अवस्था से किसी दिए गए लक्ष्य राज्य तक कभी भी पहुंचने की क्षमता निर्णायक होती है, जबकि संभाव्यता का अनुमान भी लगाया जाता है किसी दिए गए लक्ष्य राज्य तक पहुंचने के लिए (मानक एकाग्रता-आधारित संभावना जिसके लिए प्रतिक्रिया आगे होगी) का उपयोग करना अनिर्णीत है। अधिक विशेष रूप से, एक सीमित ट्यूरिंग मशीन सभी समय के लिए सही ढंग से चलने की अक्रमतः उच्च संभावना के साथ सिम्युलेटेड किया जा सकता है, केवल तभी जब एक यादृच्छिक रासायनिक प्रतिक्रिया नेटवर्क का उपयोग किया जाता है। एक सरल गैर-नियतात्मक रासायनिक प्रतिक्रिया नेटवर्क (आगे कोई भी संभावित प्रतिक्रिया हो सकती है) के साथ, कम्प्यूटेशनल शक्ति आदिम पुनरावर्ती तक सीमित है।

यह भी देखें

• एल्गोरिदम का संभाव्य विश्लेषण
• अटलांटिक सिटी एल्गोरिदम
• मोंटे कार्लो एल्गोरिथम
• लास वेगास एल्गोरिथम
• बोगोसॉर्ट
• स्थगित निर्णय का सिद्धांत
• शून्य-योग गेम के रूप में यादृच्छिक एल्गोरिदम
• संभाव्य रोडमैप
• हाइपरलॉग
• गिनती-मिनट स्केच
• अनुमानित गिनती एल्गोरिथ्म
• कार्गर का एल्गोरिदम

संदर्भ

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw–Hill, 1990. ISBN 0-262-03293-7. Chapter 5: Probabilistic Analysis and Randomized Algorithms, pp. 91–122.
• Dirk Draheim. "Semantics of the Probabilistic Typed Lambda Calculus (Markov Chain Semantics, Termination Behavior, and Denotational Semantics)." Springer, 2017.
• Jon Kleinberg and Éva Tardos. Algorithm Design. Chapter 13: "Randomized algorithms".
• Fallis, D. (2000). "The reliability of randomized algorithms". The British Journal for the Philosophy of Science. 51 (2): 255–271. doi:10.1093/bjps/51.2.255.
• M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York (NY), 2005.
• Rajeev Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, New York (NY), 1995.
• Rajeev Motwani and P. Raghavan. Randomized Algorithms. A survey on Randomized Algorithms.
• Christos Papadimitriou (1993), Computational Complexity (1st ed.), Addison Wesley, ISBN 978-0-201-53082-7 Chapter 11: Randomized computation, pp. 241–278.
• Rabin, Michael O. (1980). "Probabilistic algorithm for testing primality". Journal of Number Theory. 12: 128–138. doi:10.1016/0022-314X(80)90084-0.
• A. A. Tsay, W. S. Lovejoy, David R. Karger, Random Sampling in Cut, Flow, and Network Design Problems, Mathematics of Operations Research, 24(2):383–413, 1999.
• "Randomized Algorithms for Scientific Computing" (RASC), OSTI.GOV (July 10th, 2021).