संचार जटिलता: Difference between revisions

   | 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> की गणना करने के चतुर विधि खोजने का है। ध्यान दें कि, [[कम्प्यूटेशनल जटिलता सिद्धांत|संगणनात्मक जटिलता सिद्धांत]] के विपरीत, संचार जटिलता ऐलिस या बॉब द्वारा निष्पादित संगणनात्मक जटिलता या उपयोग की जाने वाली [[ स्मृति |मेमोरी]] के आकार से संबंधित नहीं है, क्योंकि हम सामान्यतः ऐलिस या बॉब की संगणनात्मक शक्ति के विषय में कुछ भी नहीं मानते हैं।

दो पक्षों के साथ यह सार समस्या (जिसे दो-पक्षीय संचार जटिलता कहा जाता है), और बहुपक्षीय संचार जटिलता के साथ इसका सामान्य रूप, कई संदर्भों में प्रासंगिक है। [[वीएलएसआई]] परिपथ डिजाइन में, उदाहरण के लिए, एक वितरित संगणना के समय विभिन्न घटकों के बीच पारित विद्युत संकेतों की मात्रा को कम करके उपयोग की जाने वाली ऊर्जा को कम करना चाहता है। समस्या डेटा संरचनाओं के अध्ययन और कंप्यूटर नेटवर्क के अनुकूलन में भी प्रासंगिक है। क्षेत्र के सर्वेक्षणों के लिए, {{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</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>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>k</math> बिट्स का पहले ही आदान-प्रदान हो चुका है। अब, एक विशेष के लिए <math>h \in \{0,1\}^k</math>, आइए एक आव्यूह को परिभाषित करें

फिर, <math>T_{h} \subseteq X \times Y</math>, और यह दिखाना कठिन नहीं है कि <math>T_{h}</math> <math>A</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> के स्तंभों का प्रतिनिधित्व करती हैं।

जैसा कि आप देख सकते हैं, फलन मात्र 1 का मूल्यांकन करता है जब <math>x</math> <math>y</math> के बराबर होता है (अर्थात, विकर्ण पर)। यह देखना भी अत्यधिक सरल है कि कैसे एक बिट संचार आपकी संभावनाओं को आधे में विभाजित करता है। यदि आप जानते हैं कि <math>y</math> का पहला बिट 1 है, तो आपको मात्र आधे स्तंभों पर विचार करने की आवश्यकता है (जहाँ <math>y</math> 100, 101, 110 या 111 के बराबर हो सकता है)।

प्रमाण। मान लीजिए कि <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>। यह एक निराकरण उत्पन्न करता है।

फलन <math>f</math> के लिए एक यादृच्छिक प्रोटोकॉल <math>R</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>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> के बराबर नहीं होता है। इसकी यथार्थता बढ़ाने के लिए एल्गोरिदम को कई बार दोहराया जा सकता है। यह एक यादृच्छिक संचार एल्गोरिदम के लिए आवश्यकताओं को पूरा करता है।

इससे पता चलता है कि यदि ऐलिस और बॉब लंबाई n की एक यादृच्छिक स्ट्रिंग साझा करते हैं, तो वे <math>EQ(x,y)</math> की गणना करने के लिए एक दूसरे को एक बिट भेज सकते हैं। अगले भाग में, यह दिखाया गया है कि ऐलिस और बॉब मात्र {{tmath|O(\log n)}} बिट्स का आदान-प्रदान कर सकते हैं जो लंबाई n की एक यादृच्छिक स्ट्रिंग साझा करने के समान हैं। एक बार जो दिखाया गया है, यह इस प्रकार है कि ईक्यू की गणना {{tmath|O(\log n)}} संदेशों में की जा सकती है।

यादृच्छिक प्रोटोकॉल बनाना सरल होता है जब दोनों पक्षों के निकट एक ही यादृच्छिक स्ट्रिंग (साझा स्ट्रिंग प्रोटोकॉल) तक पहुंच होती है। इन प्रोटोकॉल का उपयोग तब भी संभव है जब दोनों पक्ष एक छोटी सी संचार लागत के साथ एक यादृच्छिक स्ट्रिंग (व्यक्तिगत स्ट्रिंग प्रोटोकॉल) साझा नहीं करते हैं। किसी भी संख्या में यादृच्छिक स्ट्रिंग का उपयोग करने वाले किसी भी साझा स्ट्रिंग यादृच्छिक प्रोटोकॉल को एक व्यक्तिगत स्ट्रिंग प्रोटोकॉल द्वारा अनुकरण किया जा सकता है जो अतिरिक्त 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> चुनता है और फिर साझा यादृच्छिक स्ट्रिंग के रूप में <math>r_i</math> का उपयोग करके P चलाता है। यह <math>r_i</math> की पसंद को संप्रेषित करने के लिए O(log 100n) = O(log n) बिट्स लेता है।

एक निश्चित <math>(x,y)</math> के लिए, हम निम्नलिखित समीकरण प्राप्त करने के लिए होफ़डिंग की असमानता का उपयोग कर सकते हैं:

पहला एक क्वेट-संचार मॉडल है, जहां पक्ष शास्त्रीय संचार के अतिरिक्त क्वांटम संचार का उपयोग कर सकती हैं, उदाहरण के लिए एक [[ प्रकाशित तंतु |प्रकाशित तंतु]] के माध्यम से फोटॉन का आदान-प्रदान करके।

अलग विधि से देखने पर, यह 0/1-आव्यूह की सभी 1-प्रविष्टियों को कॉम्बीनेटरियल 1-आयत (अर्थात, गैर-सन्निहित, गैर-उत्तल सबमैट्रिसेस द्वारा कवर करने के बराबर है, जिनकी प्रविष्टियाँ सभी एक हैं (कुशीलेविट्ज़ और निसान या डायट्ज़फेलबिंगर एट अल देखें। ))। गैर-नियतात्मक संचार जटिलता आव्यूह की संख्या को कवर करने वाले आयत का द्विआधारी लघुगणक है: किसी भी 0-प्रविष्टियों को कवर किए बिना, आव्यूह की सभी 1-प्रविष्टियों को कवर करने के लिए आवश्यक कॉम्बिनेटरियल 1-आयत की न्यूनतम संख्या।

नियतात्मक संचार जटिलता के लिए कम सीमा प्राप्त करने के साधन के रूप में गैर-नियतात्मक संचार जटिलता उत्पन्न होती है (डाइट्ज़फेलबिंगर एट अल देखें), परन्तु गैर-नकारात्मक मैट्रिसेस के सिद्धांत में भी, जहां यह एक गैर-नकारात्मक आव्यूह के [[गैर-नकारात्मक रैंक (रैखिक बीजगणित)]] पर एक निचली सीमा देता है। ।<ref>{{Cite journal|author=Yannakakis, M. |title=रेखीय कार्यक्रमों द्वारा संयोजी इष्टतमीकरण समस्याओं को व्यक्त करना|journal=J. Comput. Syst. Sci.|volume=43 |issue=3 |pages=441–466 |year=1991 |doi=10.1016/0022-0000(91)90024-y|doi-access=free }}</ref>

असीमित-त्रुटि समुच्चयिंग में, ऐलिस और बॉब के निकट एक व्यक्तिगत सिक्के और उनके स्वयं के निवेश तक पहुंच होती है <math>(x, y)</math>। इस समुच्चयिंग में, ऐलिस सफल होती है यदि वह के उचित मान के साथ प्रतिक्रिया करती है <math>f(x, y)</math> संभाव्यता के साथ सख्ती से 1/2 से अधिक। दूसरे शब्दों में, यदि ऐलिस की प्रतिक्रियाओं का वास्तविक मान से कोई गैर-शून्य संबंध है <math>f(x, y)</math>, तो प्रोटोकॉल को वैध माना जाता है।

ध्यान दें कि आवश्यकता है कि सिक्का व्यक्तिगत है आवश्यक है। विशेष रूप से, यदि ऐलिस और बॉब के बीच साझा किए गए सार्वजनिक बिट्स की संख्या को संचार जटिलता के विरुद्ध नहीं गिना जाता है, तो यह तर्क देना सरल है कि किसी भी कार्य की गणना करना <math>O(1)</math> संचार जटिलता।<ref>{{Citation|last=Lovett|first=Shachar|title=CSE 291: Communication Complexity, Winter 2019 Unbounded-error protocols|url=https://cseweb.ucsd.edu/classes/wi19/cse291-b/4-unbounded.pdf|access-date=June 9, 2019}}</ref> दूसरी ओर, दोनों मॉडल समान हैं यदि ऐलिस और बॉब द्वारा उपयोग किए जाने वाले सार्वजनिक बिट्स की संख्या को प्रोटोकॉल के कुल संचार के विरुद्ध गिना जाता है।<ref>{{Cite journal|last1=Göös|first1=Mika|last2=Pitassi|first2=Toniann|last3=Watson|first3=Thomas|date=2018-06-01|title=संचार जटिलता वर्गों का परिदृश्य|journal=Computational Complexity|volume=27|issue=2|pages=245–304|doi=10.1007/s00037-018-0166-6|s2cid=4333231|issn=1420-8954|url=https://drops.dagstuhl.de/opus/volltexte/2016/6199/}}</ref>

फोरस्टर<ref>{{Cite journal|author=Forster, Jürgen |title=असीमित त्रुटि संभाव्य संचार जटिलता पर एक रैखिक निचली सीमा|journal=Journal of Computer and System Sciences |volume=65 |issue=4 |pages= 612–625 |year=2002 |doi=10.1016/S0022-0000(02)00019-3|doi-access=free }}</ref> इस वर्ग के लिए स्पष्ट निचली सीमा सिद्ध करने वाले पहले व्यक्ति थे, जो आंतरिक उत्पाद की गणना दिखा रहे थे <math>\langle x, y \rangle</math> कम से कम की आवश्यकता है <math>\Omega(n)</math> संचार के बिट्स, हालांकि एलोन, फ्रैंकल और रोडल के पहले के परिणाम ने सिद्ध कर दिया कि लगभग सभी बूलियन कार्यों के लिए संचार जटिलता <math>f: \{0, 1\}^n \times \{0, 1\}^n \to \{0, 1\}</math> है <math>\Omega(n)</math>।<ref>{{Cite journal|last1=Alon|first1=N.|last2=Frankl|first2=P.|last3=Rodl|first3=V.|date=October 1985|title=सेट सिस्टम और संभाव्य संचार जटिलता का ज्यामितीय अहसास|journal=26th Annual Symposium on Foundations of Computer Science (SFCS 1985)|location=Portland, OR, USA|publisher=IEEE|pages=277–280|doi=10.1109/SFCS.1985.30|isbn=9780818606441|citeseerx=10.1.1.300.9711|s2cid=8416636}}</ref>