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

[[सैद्धांतिक कंप्यूटर विज्ञान]] में, संचार जटिलता एक समस्या को हल करने के लिए आवश्यक संचार की मात्रा का अध्ययन करती है जब समस्या के निवेश को दो या दो से अधिक दलों के बीच संगणना वितरित किया जाता है। संचार जटिलता का अध्ययन पहली बार 1979 में [[एंड्रयू याओ]] द्वारा प्रस्तुत किया गया था, जब कई मशीनों के बीच गणना की समस्या का अध्ययन किया गया था।<ref name=yao1979>{{Citation

   | 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> को एक (combinatorial) आयत कहा जाता है यदि जब भी <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>R = M \times N</math> कुछ के लिए <math>M \subseteq X</math> और <math>N \subseteq Y</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>।

! EQ

जैसा कि आप देख सकते हैं, फलन केवल 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>। यह एक विरोधाभास पैदा करता है।

निर्धारक संचार निचली सीमाओं को साबित करने की इस तकनीक को मूर्ख समुच्चय तकनीक कहा जाता है।<ref name=":0">{{cite book| last1=Kushilevitz | first1=Eyal

उपरोक्त परिभाषा में, हम उन बिट्स की संख्या से संबंधित हैं जिन्हें निश्चित रूप से दो पक्षों के बीच प्रेषित किया जाना चाहिए। यदि दोनों पक्षों को एक यादृच्छिक संख्या जनरेटर तक पहुंच दी जाती है, तो क्या वे इसका मान निर्धारित कर सकते हैं <math>f</math> बहुत कम सूचनाओं के आदान-प्रदान के साथ? याओ, अपने सेमिनल पेपर में<ref name=yao1979/>यादृच्छिक संचार जटिलता को परिभाषित करके इस प्रश्न का उत्तर दें।

एक यादृच्छिक प्रोटोकॉल <math>R</math> एक फलन के लिए <math>f</math> दो तरफा त्रुटि है।

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

ध्यान दें कि उपरोक्त प्रायिकता असमानताओं में, प्रोटोकॉल के परिणाम को केवल यादृच्छिक स्ट्रिंग पर निर्भर समझा जाता है; दोनों तार x और y स्थिर रहते हैं। दूसरे शब्दों में, यदि यादृच्छिक स्ट्रिंग आर का उपयोग करते समय आर (एक्स, वाई) जी (एक्स, वाई, आर) उत्पन्न करता है, तो जी (एक्स, वाई, आर) = एफ (एक्स, वाई) कम से कम 2/3 के लिए स्ट्रिंग आर के लिए विकल्प।

यादृच्छिक जटिलता को ऐसे प्रोटोकॉल में एक्सचेंज किए गए बिट्स की संख्या के रूप में परिभाषित किया जाता है।

ध्यान दें कि एकतरफा त्रुटि के साथ एक यादृच्छिक प्रोटोकॉल को परिभाषित करना भी संभव है, और जटिलता को इसी तरह परिभाषित किया गया है।

EQ के पिछले उदाहरण पर लौटते हुए, यदि निश्चितता की आवश्यकता नहीं है, ऐलिस और बॉब केवल का उपयोग करके समानता की जाँच कर सकते हैं {{tmath|O(\log n)}} संदेश। निम्नलिखित प्रोटोकॉल पर विचार करें: मान लें कि ऐलिस और बॉब दोनों के निकट एक ही यादृच्छिक स्ट्रिंग तक पहुंच है <math>z \in \{0,1\}^n</math>। ऐलिस गणना करता है <math>z \cdot x</math> और बॉब को यह बिट (इसे बी कहते हैं) भेजता है। ( <math>(\cdot)</math> h> परिमित क्षेत्र में [[डॉट उत्पाद]] है#कुछ छोटे परिमित क्षेत्र|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>, जो बॉब को गलत उत्तर देगा। यह कैसे होता है?

कहाँ {{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>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> होने की समान संभावना है {{val|0}} या {{val|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 की एक यादृच्छिक स्ट्रिंग साझा करने के समान हैं। एक बार जो दिखाया गया है, यह इस प्रकार है कि EQ की गणना की जा सकती है {{tmath|O(\log n)}} संदेश।

यादृच्छिक संचार जटिलता के एक और उदाहरण के लिए, हम [[गैप-हैमिंग समस्या]] (संक्षिप्त जीएच) के रूप में ज्ञात एक उदाहरण की ओर मुड़ते हैं। विधिवत रूप से, ऐलिस और बॉब दोनों बाइनरी संदेश बनाए रखते हैं, <math>x,y \in \{-1, +1\}^n</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> संचार के लायक बिट्स, जो अनिवार्य रूप से उन सभी को कहना है।

=== सार्वजनिक सिक्के बनाम निजी सिक्के ===

यादृच्छिक प्रोटोकॉल बनाना आसान होता है जब दोनों पक्षों के निकट एक ही यादृच्छिक स्ट्रिंग (साझा स्ट्रिंग प्रोटोकॉल) तक पहुंच होती है। इन प्रोटोकॉल का उपयोग तब भी संभव है जब दोनों पक्ष एक छोटी सी संचार लागत के साथ एक यादृच्छिक स्ट्रिंग (निजी स्ट्रिंग प्रोटोकॉल) साझा नहीं करते हैं। किसी भी संख्या में यादृच्छिक स्ट्रिंग का उपयोग करने वाले किसी भी साझा स्ट्रिंग यादृच्छिक प्रोटोकॉल को एक निजी स्ट्रिंग प्रोटोकॉल द्वारा अनुकरण किया जा सकता है जो अतिरिक्त ओ (लॉग एन) बिट्स का उपयोग करता है।

सहज रूप से, हम स्ट्रिंग्स के कुछ समुच्चय पा सकते हैं जिनमें त्रुटि में केवल थोड़ी सी वृद्धि के साथ यादृच्छिक प्रोटोकॉल को चलाने के लिए पर्याप्त यादृच्छिकता है। इस समुच्चय को पहले से साझा किया जा सकता है, और एक यादृच्छिक स्ट्रिंग को चित्रित करने के बजाय, ऐलिस और बॉब को