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

"यादृच्छिक एल्गोरिदम" 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 के बीच किनारों की न्यूनतम संख्या होती है।

याद रखें कि एक (बहु-) ग्राफ़ में दो नोड्स, u और v के किनारे का संकुचन, किनारों के साथ नया नोड u' देता है, जो u या v पर किनारों की घटना का संघ है, किसी भी किनारे को छोड़कर u और v को जोड़ता है। चित्र 1 शीर्ष A और B के संकुचन का उदाहरण देता है।

संकुचन के बाद, परिणामी ग्राफ़ में समानांतर किनार हो सकते हैं, लेकिन इसमें कोई सेल्फ लूप नहीं होता है।

चित्र 2: 10-शीर्ष ग्राफ़ पर कार्गर के एल्गोरिथम का सफल संचालन। न्यूनतम कट का आकार 3 है और इसे शीर्ष रंगों द्वारा दर्शाया गया है।

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

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

    begin

i = 1
    repeat
        repeat
            Take a random edge (u,v) ∈ E in G
            replace u and v with the contraction u'
        until only 2 nodes remain
        obtain the corresponding cut result Ci
        i = i + 1
    until i = m
    output the minimum cut among C1, C2, ..., Cm.
end

बाहरी लूप के प्रत्येक निष्पादन में, एल्गोरिथ्म आंतरिक लूप को तब तक दोहराता है जब तक कि केवल 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}}$.

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

$$\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)$ पाता है।

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

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

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

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

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

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

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

यह भी देखें

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

संदर्भ

• 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).