संचार जटिलता: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (6 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
{{Short description|Complexity of sending information in a distributed algorithm}} | {{Short description|Complexity of sending information in a distributed algorithm}} | ||
[[सैद्धांतिक कंप्यूटर विज्ञान]] में, संचार जटिलता एक समस्या को हल करने के लिए आवश्यक संचार की मात्रा का अध्ययन करती है जब समस्या के निवेश को दो या दो से अधिक | [[सैद्धांतिक कंप्यूटर विज्ञान]] में, संचार जटिलता एक समस्या को हल करने के लिए आवश्यक संचार की मात्रा का अध्ययन करती है जब समस्या के निवेश को दो या दो से अधिक पक्षों के बीच संगणना वितरित किया जाता है। संचार जटिलता का अध्ययन पहली बार 1979 में [[एंड्रयू याओ]] द्वारा प्रस्तुत किया गया था, जब कई मशीनों के बीच गणना की समस्या का अध्ययन किया गया था।<ref name=yao1979>{{Citation | ||
| last = Yao | | last = Yao | ||
| first = A. C. | | first = A. C. | ||
| Line 8: | Line 8: | ||
| volume = 14 | | volume = 14 | ||
| pages = 209–213 | | pages = 209–213 | ||
| year = 1979 }}</ref> समस्या को सामान्यतः निम्नानुसार कहा जाता है: दो पक्ष (परंपरागत रूप से [[ऐलिस और बॉब]] कहलाते हैं) प्रत्येक को एक (संभावित रूप से भिन्न) <math>n</math>-[[ अंश | अंश]] स्ट्रिंग <math>x</math> और <math>y</math> प्राप्त होता है। लक्ष्य ऐलिस के लिए एक निश्चित फलन <math>f(x, y)</math> के मान की गणना करना है, जो <math>x</math> और <math>y</math> दोनों पर निर्भर | | year = 1979 }}</ref> समस्या को सामान्यतः निम्नानुसार कहा जाता है: दो पक्ष (परंपरागत रूप से [[ऐलिस और बॉब]] कहलाते हैं) प्रत्येक को एक (संभावित रूप से भिन्न) <math>n</math>-[[ अंश | अंश]] स्ट्रिंग <math>x</math> और <math>y</math> प्राप्त होता है। लक्ष्य ऐलिस के लिए एक निश्चित फलन <math>f(x, y)</math> के मान की गणना करना है, जो <math>x</math> और <math>y</math> दोनों पर निर्भर करते है, उनके बीच [[संचार]] की कम से कम मात्रा के साथ है। | ||
जबकि ऐलिस और बॉब हमेशा ऐलिस को अपनी पूरी <math>n</math> बिट स्ट्रिंग भेजकर सफल हो सकते हैं (जो तब फलन (गणित) <math>f</math> की गणना करता है) ), यहाँ विचार <math>n</math> बिट्स से कम संचार के साथ <math>f</math> की गणना करने के चतुर विधि खोजने का है। ध्यान दें कि, [[कम्प्यूटेशनल जटिलता सिद्धांत|संगणनात्मक जटिलता सिद्धांत]] के विपरीत, संचार जटिलता ऐलिस या बॉब द्वारा निष्पादित संगणनात्मक जटिलता या उपयोग की जाने वाली [[ स्मृति |मेमोरी]] के आकार से संबंधित नहीं है, क्योंकि हम सामान्यतः ऐलिस या बॉब की संगणनात्मक शक्ति के विषय में कुछ भी नहीं मानते हैं। | जबकि ऐलिस और बॉब हमेशा ऐलिस को अपनी पूरी <math>n</math> बिट स्ट्रिंग भेजकर सफल हो सकते हैं (जो तब फलन (गणित) <math>f</math> की गणना करता है)), यहाँ विचार <math>n</math> बिट्स से कम संचार के साथ <math>f</math> की गणना करने के चतुर विधि खोजने का है। ध्यान दें कि, [[कम्प्यूटेशनल जटिलता सिद्धांत|संगणनात्मक जटिलता सिद्धांत]] के विपरीत, संचार जटिलता ऐलिस या बॉब द्वारा निष्पादित संगणनात्मक जटिलता या उपयोग की जाने वाली [[ स्मृति |मेमोरी]] के आकार से संबंधित नहीं है, क्योंकि हम सामान्यतः ऐलिस या बॉब की संगणनात्मक शक्ति के विषय में कुछ भी नहीं मानते हैं। | ||
दो पक्षों के साथ यह सार समस्या (जिसे दो-पक्षीय संचार जटिलता कहा जाता है), और बहुपक्षीय संचार जटिलता के साथ इसका सामान्य रूप, कई संदर्भों में प्रासंगिक है। [[वीएलएसआई]] परिपथ डिजाइन में, उदाहरण के लिए, | दो पक्षों के साथ यह सार समस्या (जिसे दो-पक्षीय संचार जटिलता कहा जाता है), और बहुपक्षीय संचार जटिलता के साथ इसका सामान्य रूप, कई संदर्भों में प्रासंगिक है। [[वीएलएसआई]] परिपथ डिजाइन में, उदाहरण के लिए, वितरित संगणना के समय विभिन्न घटकों के बीच पारित विद्युत संकेतों की मात्रा को कम करके उपयोग की जाने वाली ऊर्जा को कम करना चाहता है। समस्या डेटा संरचनाओं के अध्ययन और कंप्यूटर नेटवर्क के अनुकूलन में भी प्रासंगिक है। क्षेत्र के सर्वेक्षणों के लिए, {{harvtxt|राव|येहुदयॉफ़|2020}} और {{harvtxt|कुशीलेविट्ज़|निसान|2006}} की पाठ्यपुस्तकें देखें। | ||
== विधिवत परिभाषा == | == विधिवत परिभाषा == | ||
आइए <math>f: X \times Y \rightarrow Z</math> जहां हम विशिष्ट स्थिति में मानते हैं कि <math> X=Y=\{0,1\}^n </math> और <math> Z=\{0,1\}</math>। ऐलिसके निकट <math>n</math>-बिट स्ट्रिंग <math>x \in X</math> है जबकि बॉब के निकट <math>n</math>-बिट स्ट्रिंग <math>y \in Y</math>है। एक समय में एक दूसरे से संचार करके (कुछ संचार प्रोटोकॉल को अपनाते हुए जो पहले से सहमत हैं), ऐलिस और बॉब <math>f(x,y)</math>के मान की गणना करना चाहते हैं जैसे कि कम से कम | आइए <math>f: X \times Y \rightarrow Z</math> जहां हम विशिष्ट स्थिति में मानते हैं कि <math> X=Y=\{0,1\}^n </math> और <math> Z=\{0,1\}</math>। ऐलिसके निकट <math>n</math>-बिट स्ट्रिंग <math>x \in X</math> है जबकि बॉब के निकट <math>n</math>-बिट स्ट्रिंग <math>y \in Y</math>है। एक समय में एक दूसरे से संचार करके (कुछ संचार प्रोटोकॉल को अपनाते हुए जो पहले से सहमत हैं), ऐलिस और बॉब <math>f(x,y)</math>के मान की गणना करना चाहते हैं जैसे कि कम से कम पक्ष संचार के अंत में मान जानता है। इस बिंदु पर उत्तर को वापस संप्रेषित किया जा सकता है ताकि अतिरिक्त बिट के मान पर दोनों पक्षों को उत्तर पता चल सके। कंप्यूटिंग <math>f</math> की इस संचार समस्या का सबसे निकृष्ट स्थिति संचार जटिलता, जिसे <math> D(f) </math>के रूप में दर्शाया गया है, को तब परिभाषित किया गया है | ||
:<math> D(f) = </math> सबसे निकृष्ट स्थिति में ऐलिस और बॉब के बीच न्यूनतम बिट्स का आदान-प्रदान। | :<math> D(f) = </math> सबसे निकृष्ट स्थिति में ऐलिस और बॉब के बीच न्यूनतम बिट्स का आदान-प्रदान। | ||
जैसा कि ऊपर देखा गया है, किसी भी फलन <math>f: \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}</math> के लिए , अपने निकट <math>D(f) \leq n</math> है। उपरोक्त परिभाषा का उपयोग करते हुए, फलन <math>f</math> को आव्यूह <math>A</math> (निवेश आव्यूह या संचार आव्यूह कहा जाता है) के रूप में सोचना उपयोगी | जैसा कि ऊपर देखा गया है, किसी भी फलन <math>f: \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}</math> के लिए, अपने निकट <math>D(f) \leq n</math> है। उपरोक्त परिभाषा का उपयोग करते हुए, फलन <math>f</math> को आव्यूह <math>A</math> (निवेश आव्यूह या संचार आव्यूह कहा जाता है) के रूप में सोचना उपयोगी होते है, जहां पंक्तियों को <math>x \in X</math> और स्तंभों को <math>y \in Y</math>द्वारा अनुक्रमित किया जाता है। आव्यूह की प्रविष्टियाँ <math>A_{x,y}=f(x,y)</math> हैं। प्रारंभ में ऐलिस और बॉब दोनों के निकट संपूर्ण आव्यूह <math>A</math> की एक प्रति है (यह मानते हुए कि फलन <math>f</math> दोनों पक्षों को ज्ञात है)। फिर, फलन मान की गणना करने की समस्या को संबंधित आव्यूह प्रविष्टि पर शून्यीकरण-में के रूप में दोहराया जा सकता है। इस समस्या को हल किया जा सकता है यदि ऐलिस या बॉब <math>x</math> और <math>y</math> दोनों को जानते हैं। संचार की प्रारम्भ में, निवेश पर फलन के मान के लिए विकल्पों की संख्या आव्यूह का आकार, अर्थात <math>2^{2n}</math> है। फिर, जब और जब प्रत्येक पक्ष दूसरे से थोड़ा संवाद करता है, तो उत्तर के लिए विकल्पों की संख्या कम हो जाती है क्योंकि यह पंक्तियों/स्तंभों के एक समुच्चय को समाप्त कर देते है जिसके परिणामस्वरूप <math>A</math> का उपआव्यूह होता है। | ||
अधिक विधिवत रूप से, एक समुच्चय <math>R \subseteq X \times Y</math> को एक (सांयोगिक) आयत कहा जाता है यदि जब भी <math>(x_1,y_1) \in R</math> और <math>(x_2,y_2) \in R</math> तब <math>(x_1,y_2) \in R</math> हो। समान रूप से, <math>R</math> एक संयोजी आयत है यदि इसे कुछ <math>M \subseteq X</math> और <math>N \subseteq Y</math> के लिए <math>R = M \times N</math> के रूप में व्यक्त किया जा सकता है। उस स्थिति पर विचार करें जब | अधिक विधिवत रूप से, एक समुच्चय <math>R \subseteq X \times Y</math> को एक (सांयोगिक) आयत कहा जाता है यदि जब भी <math>(x_1,y_1) \in R</math> और <math>(x_2,y_2) \in R</math> तब <math>(x_1,y_2) \in R</math> हो। समान रूप से, <math>R</math> एक संयोजी आयत है यदि इसे कुछ <math>M \subseteq X</math> और <math>N \subseteq Y</math> के लिए <math>R = M \times N</math> के रूप में व्यक्त किया जा सकता है। उस स्थिति पर विचार करें जब पक्षों के बीच <math>k</math> बिट्स का पहले ही आदान-प्रदान हो चुका है। अब, विशेष के लिए <math>h \in \{0,1\}^k</math>, आइए आव्यूह को परिभाषित करें | ||
:<math>T_{h} = \{ (x, y) : \text{ the }k\text{-bits exchanged on input } (x , y) \text{ is }h\}</math> | :<math>T_{h} = \{ (x, y) : \text{ the }k\text{-bits exchanged on input } (x , y) \text{ is }h\}</math> | ||
फिर, <math>T_{h} \subseteq X \times Y</math>, और यह दिखाना कठिन नहीं है कि <math>T_{h}</math> <math>A</math> में एक संयुक्त आयत | फिर, <math>T_{h} \subseteq X \times Y</math>, और यह दिखाना कठिन नहीं है कि <math>T_{h}</math> <math>A</math> में एक संयुक्त आयत है। | ||
=== उदाहरण: <math>EQ</math> === | === उदाहरण: <math>EQ</math> === | ||
हम उस स्थिति पर विचार करते हैं जहां ऐलिस और बॉब यह निर्धारित करने का प्रयास करते हैं कि उनके निवेश | हम उस स्थिति पर विचार करते हैं जहां ऐलिस और बॉब यह निर्धारित करने का प्रयास करते हैं कि उनके निवेश स्ट्रिंग्स बराबर हैं या नहीं। विधिवत रूप से, समानता फलन को परिभाषित करें, जिसे <math>EQ : \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}</math> द्वारा दर्शाया गया है, <math>EQ(x, y) = 1</math> यदि <math>x = y</math> है। जैसा कि हम नीचे प्रदर्शित करते हैं, <math>EQ</math> को हल करने वाले किसी भी निर्धारक संचार प्रोटोकॉल को सबसे निकृष्ट स्थिति में संचार के <math>n</math> बिट्स की आवश्यकता होती है। अनुकूलन उदाहरण के रूप में, <math>x, y \in \{0, 1\}^3</math> के साधारण स्थिति पर विचार करें। इस स्थिति में समानता फलन नीचे आव्यूह द्वारा दर्शाया जा सकता है। पंक्तियाँ <math>x</math> की सभी संभावनाओं को <math>y</math> के स्तंभों का प्रतिनिधित्व करती हैं। | ||
{| class="wikitable" style="font-family: monospace; text-align: right; margin-left: auto; margin-right: auto; border: none;" | {| class="wikitable" style="font-family: monospace; text-align: right; margin-left: auto; margin-right: auto; border: none;" | ||
! | ! ईक्यू | ||
! 000 | ! 000 | ||
! 001 | ! 001 | ||
| Line 123: | Line 123: | ||
|- | |- | ||
|} | |} | ||
जैसा कि आप देख सकते हैं, फलन मात्र 1 का मूल्यांकन करता है जब <math>x</math> <math>y</math> के बराबर | जैसा कि आप देख सकते हैं, फलन मात्र 1 का मूल्यांकन करता है जब <math>x</math> <math>y</math> के बराबर होते है (अर्थात, विकर्ण पर)। यह देखना भी अत्यधिक सरल है कि कैसे एक बिट संचार आपकी संभावनाओं को आधे में विभाजित करता है। यदि आप जानते हैं कि <math>y</math> का पहला बिट 1 है, तो आपको मात्र आधे स्तंभों पर विचार करने की आवश्यकता है (जहाँ <math>y</math> 100, 101, 110 या 111 के बराबर हो सकते है)। | ||
=== प्रमेय: <math>D(EQ) = n</math> === | === प्रमेय: <math>D(EQ) = n</math> === | ||
प्रमाण। मान लीजिए कि <math>D(EQ) \leq n-1</math>। इसका अर्थ यह है कि वहाँ <math>x \neq x'</math> स्थित है जैसे कि <math>(x, x)</math> और <math>(x', x')</math> में समान संचार प्रतिलेख <math>h</math> है। चूंकि यह प्रतिलेख | प्रमाण। मान लीजिए कि <math>D(EQ) \leq n-1</math>। इसका अर्थ यह है कि वहाँ <math>x \neq x'</math> स्थित है जैसे कि <math>(x, x)</math> और <math>(x', x')</math> में समान संचार प्रतिलेख <math>h</math> है। चूंकि यह प्रतिलेख आयत को परिभाषित करता है, <math>f(x, x')</math> भी 1 होना चाहिए। परिभाषा के अनुसार <math>x \neq x'</math> और हम जानते हैं कि समानता मात्र <math>(a, b)</math> के लिए सत्य है जब <math>a = b</math>। यह एक निराकरण उत्पन्न करता है। | ||
निर्धारक संचार निचली सीमाओं को सिद्ध करने की इस तकनीक को मूर्ख समुच्चय तकनीक कहा जाता है।<ref name=":0">{{cite book| last1=Kushilevitz | first1=Eyal | निर्धारक संचार निचली सीमाओं को सिद्ध करने की इस तकनीक को मूर्ख समुच्चय तकनीक कहा जाता है।<ref name=":0">{{cite book| last1=Kushilevitz | first1=Eyal | ||
| Line 139: | Line 139: | ||
== यादृच्छिक संचार जटिलता == | == यादृच्छिक संचार जटिलता == | ||
उपरोक्त परिभाषा में, हम उन बिट्स की संख्या से संबंधित हैं जिन्हें निश्चित रूप से दो पक्षों के बीच प्रेषित किया जाना चाहिए। यदि दोनों पक्षों को एक यादृच्छिक संख्या | उपरोक्त परिभाषा में, हम उन बिट्स की संख्या से संबंधित हैं जिन्हें निश्चित रूप से दो पक्षों के बीच प्रेषित किया जाना चाहिए। यदि दोनों पक्षों को एक यादृच्छिक संख्या जनक तक पहुंच प्रदान की जाती है, तो क्या वे बहुत कम सूचनाओं के आदान-प्रदान के साथ <math>f</math> का मान निर्धारित कर सकते हैं? याओ, अपने सेमिनल पेपर में<ref name=yao1979/> यादृच्छिक संचार जटिलता को परिभाषित करके इस प्रश्न का उत्तर देते हैं। | ||
फलन <math>f</math> के लिए यादृच्छिक प्रोटोकॉल <math>R</math> में दो पक्षीय त्रुटि है। | |||
:<math> | :<math> | ||
| Line 149: | Line 149: | ||
\Pr[R(x,y) = 1] > \frac{2}{3}, \textrm{if }\, f(x,y) = 1 | \Pr[R(x,y) = 1] > \frac{2}{3}, \textrm{if }\, f(x,y) = 1 | ||
</math> | </math> | ||
एक यादृच्छिक प्रोटोकॉल | एक यादृच्छिक प्रोटोकॉल नियतात्मक प्रोटोकॉल है जो अपने सामान्य निवेश के अतिरिक्त एक अतिरिक्त यादृच्छिक स्ट्रिंग का उपयोग करता है। इसके लिए दो मॉडल हैं: सार्वजनिक स्ट्रिंग एक यादृच्छिक स्ट्रिंग है जिसे दोनों पक्षों द्वारा पहले से जाना जाता है, जबकि व्यक्तिगत स्ट्रिंग पक्ष द्वारा उत्पन्न की जाती है और इसे दूसरे पक्ष को सूचित किया जाना चाहिए। नीचे प्रस्तुत प्रमेय से पता चलता है कि किसी भी सार्वजनिक स्ट्रिंग प्रोटोकॉल को व्यक्तिगत स्ट्रिंग प्रोटोकॉल द्वारा अनुकरण किया जा सकता है जो मूल की तुलना में O (log n) अतिरिक्त बिट्स का उपयोग करता है। | ||
ध्यान दें कि उपरोक्त प्रायिकता असमानताओं में, प्रोटोकॉल के परिणाम को मात्र यादृच्छिक स्ट्रिंग पर निर्भर समझा जाता है; दोनों | ध्यान दें कि उपरोक्त प्रायिकता असमानताओं में, प्रोटोकॉल के परिणाम को मात्र यादृच्छिक स्ट्रिंग पर निर्भर समझा जाता है; दोनों स्ट्रिंग्स x और y स्थिर रहते हैं। दूसरे शब्दों में, यदि यादृच्छिक स्ट्रिंग r का उपयोग करते समय r (x, y) g (x, y, r) उत्पन्न करते है, फिर g (x, y, r) = f (x, y) स्ट्रिंग r के लिए सभी विकल्पों में से कम से कम 2/3 के लिए। | ||
यादृच्छिक जटिलता को ऐसे प्रोटोकॉल में | यादृच्छिक जटिलता को ऐसे प्रोटोकॉल में विनिमय किए गए बिट्स की संख्या के रूप में परिभाषित किया जाता है। | ||
ध्यान दें कि | ध्यान दें कि एकपक्षीय त्रुटि के साथ यादृच्छिक प्रोटोकॉल को परिभाषित करना भी संभव है, और जटिलता को इसी प्रकार परिभाषित किया गया है। | ||
=== उदाहरण: ईक्यू === | === उदाहरण: ईक्यू === | ||
ईक्यू के पिछले उदाहरण पर लौटते हुए, यदि निश्चितता की आवश्यकता नहीं है, ऐलिस और बॉब मात्र {{tmath|O(\log n)}}संदेशों का उपयोग करके समानता की जाँच कर सकते हैं। निम्नलिखित प्रोटोकॉल पर विचार करें: मान लें कि ऐलिस और बॉब दोनों के निकट एक ही यादृच्छिक स्ट्रिंग <math>z \in \{0,1\}^n</math> तक पहुंच है। ऐलिस <math>z \cdot x</math> की गणना करता है और बॉब को यह बिट (इसे b कहते हैं) भेजता है। (<math>(\cdot)</math> GF (2) [[डॉट उत्पाद|बिंदु उत्पाद]] है।) फिर बॉब b की तुलना <math>z \cdot y</math> से करता है। यदि वे समान हैं, तो बॉब यह कहते हुए स्वीकार करते है कि x बराबर y है। नहीं तो वह मना कर देते है। | |||
स्पष्ट रूप से, यदि <math>x = y</math>, तो <math>z \cdot x = z \cdot y</math>, इसलिए <math>Prob_z[Accept] = 1</math>। यदि x, y के बराबर नहीं है, तब भी यह संभव है कि <math>z \cdot x = z \cdot y</math>, जो बॉब को अनुचित उत्तर देगा। यह कैसे होता है? | |||
यदि x और y समान नहीं हैं, तो उन्हें कुछ स्थानों पर भिन्न होना चाहिए: | यदि x और y समान नहीं हैं, तो उन्हें कुछ स्थानों पर भिन्न होना चाहिए: | ||
| Line 170: | Line 170: | ||
z = z_1 z_2 \ldots z_i \ldots z_j \ldots z_n | z = z_1 z_2 \ldots z_i \ldots z_j \ldots z_n | ||
\end{cases}</math> | \end{cases}</math> | ||
जहाँ {{mvar|x}} और {{mvar|y}} सहमत होते हैं, <math>z_i * x_i = z_i * c_i = z_i * y_i</math> इसलिए वे प्रतिबन्ध बिंदु उत्पादों को समान रूप से प्रभावित करती हैं। हम उन प्रतिबन्धों को सुरक्षित रूप से अनदेखा कर सकते हैं और मात्र वहीं देख सकते हैं {{mvar|x}} और {{mvar|y}} अलग होना। इसके अतिरिक्त, हम बिंदु उत्पादों के बराबर हैं या नहीं, इसे बदले बिना बिट्स <math>x_i</math> और <math>y_i</math> को विनिमय कर सकते हैं। इसका अर्थ है कि हम बिट्स को विनिमय कर सकते हैं ताकि {{mvar|x}} में मात्र शून्य हो और {{mvar|y}} में मात्र एक हो: | |||
:<math>\begin{cases} | :<math>\begin{cases} | ||
| Line 177: | Line 177: | ||
z' = z_1 z_2 \ldots z_{n'} | z' = z_1 z_2 \ldots z_{n'} | ||
\end{cases}</math> | \end{cases}</math> | ||
ध्यान दें कि <math>z' \cdot x' = 0</math> और <math>z' \cdot y' = \Sigma_i z'_i</math>। अब, प्रश्न बन जाता है: कुछ यादृच्छिक स्ट्रिंग | ध्यान दें कि <math>z' \cdot x' = 0</math> और <math>z' \cdot y' = \Sigma_i z'_i</math>। अब, प्रश्न बन जाता है: कुछ यादृच्छिक स्ट्रिंग <math>z'</math> के लिए, क्या प्रायिकता है कि <math>\Sigma_i z'_i = 0</math>? चूंकि प्रत्येक <math>z'_i</math> की समान रूप से 0 या 1 होने की संभावना है, यह संभावना मात्र <math>1/2</math>है। इस प्रकार, जब {{mvar|x}}, {{mvar|y}},<math>Prob_z[Accept] = 1/2</math> के बराबर नहीं होते है। इसकी यथार्थता बढ़ाने के लिए एल्गोरिदम को कई बार दोहराया जा सकता है। यह एक यादृच्छिक संचार एल्गोरिदम के लिए आवश्यकताओं को पूरा करते है। | ||
<math>Prob_z[Accept] = 1/2</math> | |||
इससे पता चलता है कि यदि ऐलिस और बॉब लंबाई n की | इससे पता चलता है कि यदि ऐलिस और बॉब लंबाई n की यादृच्छिक स्ट्रिंग साझा करते हैं, तो वे <math>EQ(x,y)</math> की गणना करने के लिए एक दूसरे को एक बिट भेज सकते हैं। अगले भाग में, यह दिखाया गया है कि ऐलिस और बॉब मात्र {{tmath|O(\log n)}} बिट्स का आदान-प्रदान कर सकते हैं जो लंबाई n की यादृच्छिक स्ट्रिंग साझा करने के समान हैं। एक बार जो दिखाया गया है, यह इस प्रकार है कि ईक्यू की गणना {{tmath|O(\log n)}} संदेशों में की जा सकती है। | ||
=== उदाहरण: जीएच === | === उदाहरण: जीएच === | ||
यादृच्छिक संचार जटिलता के एक और उदाहरण के लिए, हम [[गैप-हैमिंग समस्या]] (संक्षिप्त जीएच) के रूप में ज्ञात एक उदाहरण की ओर मुड़ते हैं। विधिवत रूप से, ऐलिस और बॉब दोनों बाइनरी संदेश | यादृच्छिक संचार जटिलता के एक और उदाहरण के लिए, हम [[गैप-हैमिंग समस्या|अंतर-हैमिंग समस्या]] (संक्षिप्त जीएच) के रूप में ज्ञात एक उदाहरण की ओर मुड़ते हैं। विधिवत रूप से, ऐलिस और बॉब दोनों बाइनरी संदेश, <math>x,y \in \{-1, +1\}^n</math> बनाए रखते हैं और यह निर्धारित करना चाहते हैं कि स्ट्रिंग्स बहुत समान हैं या यदि वे बहुत समान नहीं हैं।विशेष रूप से, वे निम्नलिखित आंशिक बूलियन फलन की गणना करने के लिए यथासंभव कुछ बिट्स के संचरण की आवश्यकता वाले संचार प्रोटोकॉल को खोजना चाहेंगे, | ||
:<math> | :<math> | ||
| Line 191: | Line 190: | ||
+1 & \langle x, y \rangle \geq \sqrt{n}. | +1 & \langle x, y \rangle \geq \sqrt{n}. | ||
\end{cases} | \end{cases} | ||
</math> स्पष्ट रूप से, यदि प्रोटोकॉल नियतात्मक होना है, तो उन्हें अपने सभी बिट्स को संवाद करना होगा (यह इसलिए है, क्योंकि यदि कोई नियतात्मक, सख्त सूचकांकों का सबसमुच्चय है जो ऐलिस और बॉब एक दूसरे से रिले करते हैं, तो उस समुच्चय पर स्ट्रिंग्स की एक जोड़ी होने की कल्पना करें में असहमत <math>\sqrt{n} - 1</math> पदों। यदि किसी स्थिति में एक और असहमति उत्पन्न होती है जो रिलेटेड नहीं होती है, तो यह परिणाम को प्रभावित करती है <math> \text{GH}_n(x, y)</math>, और इसलिए एक | </math> | ||
:स्पष्ट रूप से, यदि प्रोटोकॉल नियतात्मक होना है, तो उन्हें अपने सभी बिट्स को संवाद करना होगा (यह इसलिए है, क्योंकि यदि कोई नियतात्मक, सख्त सूचकांकों का सबसमुच्चय है जो ऐलिस और बॉब एक दूसरे से रिले करते हैं, तो उस समुच्चय पर स्ट्रिंग्स की एक जोड़ी होने की कल्पना करें में असहमत <math>\sqrt{n} - 1</math> पदों। यदि किसी स्थिति में एक और असहमति उत्पन्न होती है जो रिलेटेड नहीं होती है, तो यह परिणाम को प्रभावित करती है <math> \text{GH}_n(x, y)</math>, और इसलिए एक अनुचित प्रक्रिया का परिणाम होगा। | |||
एक स्वाभाविक प्रश्न तब पूछा जाता है, यदि हमें <math>1/3</math> समय की त्रुटि करने की अनुमति है (यादृच्छिक उदाहरणों पर <math> x, y</math> समान रूप से <math> \{-1, +1\}^n </math>) से यादृच्छिक रूप से खींचा गया है, तो क्या हम कम बिट्स वाले प्रोटोकॉल से दूर हो सकते हैं? यह पता चला है कि 2012 में चक्रवर्ती और रेगेव के परिणाम के कारण उत्तर किंचित आश्चर्यजनक रूप से नहीं है: वे दिखाते हैं कि यादृच्छिक उदाहरणों के लिए, कोई भी प्रक्रिया जो कम से कम <math>2/3</math> समय के लिए उचित है, संचार के <math>\Omega(n)</math> बिट्स को भेजना चाहिए, जो अनिवार्य रूप से उन सभी को कहना है। | |||
=== सार्वजनिक सिक्के बनाम | === सार्वजनिक सिक्के बनाम व्यक्तिगत सिक्के === | ||
यादृच्छिक प्रोटोकॉल बनाना सरल होता है जब दोनों पक्षों के निकट एक ही यादृच्छिक स्ट्रिंग (साझा स्ट्रिंग प्रोटोकॉल) तक पहुंच होती है। इन प्रोटोकॉल का उपयोग तब भी संभव है जब दोनों पक्ष | यादृच्छिक प्रोटोकॉल बनाना सरल होता है जब दोनों पक्षों के निकट एक ही यादृच्छिक स्ट्रिंग (साझा स्ट्रिंग प्रोटोकॉल) तक पहुंच होती है। इन प्रोटोकॉल का उपयोग तब भी संभव है जब दोनों पक्ष छोटी सी संचार लागत के साथ यादृच्छिक स्ट्रिंग (व्यक्तिगत स्ट्रिंग प्रोटोकॉल) साझा नहीं करते हैं। किसी भी संख्या में यादृच्छिक स्ट्रिंग का उपयोग करने वाले किसी भी साझा स्ट्रिंग यादृच्छिक प्रोटोकॉल को व्यक्तिगत स्ट्रिंग प्रोटोकॉल द्वारा अनुकरण किया जा सकता है जो अतिरिक्त O (log n) बिट्स का उपयोग करता है। | ||
सहज रूप से, हम स्ट्रिंग्स के कुछ समुच्चय पा सकते हैं जिनमें त्रुटि में मात्र थोड़ी सी वृद्धि के साथ यादृच्छिक प्रोटोकॉल को चलाने के लिए पर्याप्त यादृच्छिकता है। इस समुच्चय को पहले से साझा किया जा सकता है, और | सहज रूप से, हम स्ट्रिंग्स के कुछ समुच्चय पा सकते हैं जिनमें त्रुटि में मात्र थोड़ी सी वृद्धि के साथ यादृच्छिक प्रोटोकॉल को चलाने के लिए पर्याप्त यादृच्छिकता है। इस समुच्चय को पहले से साझा किया जा सकता है, और यादृच्छिक स्ट्रिंग को चित्रित करने के अतिरिक्त, ऐलिस और बॉब को मात्र इस बात पर सहमत होना चाहिए कि साझा समुच्चय से किस स्ट्रिंग को चुनना है। यह समुच्चय इतना छोटा है कि पसंद को कुशलता से संप्रेषित किया जा सकता है। एक विधिवत प्रमाण इस प्रकार है। | ||
0.1 की अधिकतम त्रुटि दर के साथ कुछ यादृच्छिक प्रोटोकॉल P पर विचार करें। <math>R</math> को लंबाई n के <math>100n</math> स्ट्रिंग्स होने दें, क्रमांकित <math>r_1, r_2, \dots, r_{100n}</math>। इस प्रकार के <math>R</math> को देखते हुए, एक नवीन प्रोटोकॉल <math>P'_R</math> परिभाषित करें जो यादृच्छिक रूप से कुछ <math>r_i</math> चुनता है और फिर साझा यादृच्छिक स्ट् | |||