संचार जटिलता: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 29: | Line 29: | ||
=== उदाहरण: <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;" | ||
| Line 151: | Line 151: | ||
एक यादृच्छिक प्रोटोकॉल एक नियतात्मक प्रोटोकॉल है जो अपने सामान्य निवेश के अतिरिक्त एक अतिरिक्त यादृच्छिक स्ट्रिंग का उपयोग करता है। इसके लिए दो मॉडल हैं: एक सार्वजनिक स्ट्रिंग एक यादृच्छिक स्ट्रिंग है जिसे दोनों पक्षों द्वारा पहले से जाना जाता है, जबकि एक व्यक्तिगत स्ट्रिंग एक पक्ष द्वारा उत्पन्न की जाती है और इसे दूसरे पक्ष को सूचित किया जाना चाहिए। नीचे प्रस्तुत एक प्रमेय से पता चलता है कि किसी भी सार्वजनिक स्ट्रिंग प्रोटोकॉल को एक व्यक्तिगत स्ट्रिंग प्रोटोकॉल द्वारा अनुकरण किया जा सकता है जो मूल की तुलना में O(log n) अतिरिक्त बिट्स का उपयोग करता है। | एक यादृच्छिक प्रोटोकॉल एक नियतात्मक प्रोटोकॉल है जो अपने सामान्य निवेश के अतिरिक्त एक अतिरिक्त यादृच्छिक स्ट्रिंग का उपयोग करता है। इसके लिए दो मॉडल हैं: एक सार्वजनिक स्ट्रिंग एक यादृच्छिक स्ट्रिंग है जिसे दोनों पक्षों द्वारा पहले से जाना जाता है, जबकि एक व्यक्तिगत स्ट्रिंग एक पक्ष द्वारा उत्पन्न की जाती है और इसे दूसरे पक्ष को सूचित किया जाना चाहिए। नीचे प्रस्तुत एक प्रमेय से पता चलता है कि किसी भी सार्वजनिक स्ट्रिंग प्रोटोकॉल को एक व्यक्तिगत स्ट्रिंग प्रोटोकॉल द्वारा अनुकरण किया जा सकता है जो मूल की तुलना में O(log n) अतिरिक्त बिट्स का उपयोग करता है। | ||
ध्यान दें कि उपरोक्त प्रायिकता असमानताओं में, प्रोटोकॉल के परिणाम को मात्र यादृच्छिक स्ट्रिंग पर निर्भर समझा जाता है; दोनों | ध्यान दें कि उपरोक्त प्रायिकता असमानताओं में, प्रोटोकॉल के परिणाम को मात्र यादृच्छिक स्ट्रिंग पर निर्भर समझा जाता है; दोनों स्ट्रिंग्स x और y स्थिर रहते हैं। दूसरे शब्दों में, यदि यादृच्छिक स्ट्रिंग r का उपयोग करते समय r (x, y) g (x, y, r) उत्पन्न करता है, फिर g (x, y, r) = f (x, y) स्ट्रिंग r के लिए सभी विकल्पों में से कम से कम 2/3 के लिए। | ||
यादृच्छिक जटिलता को ऐसे प्रोटोकॉल में विनिमय किए गए बिट्स की संख्या के रूप में परिभाषित किया जाता है। | यादृच्छिक जटिलता को ऐसे प्रोटोकॉल में विनिमय किए गए बिट्स की संख्या के रूप में परिभाषित किया जाता है। | ||
| Line 182: | Line 182: | ||
=== उदाहरण: जीएच === | === उदाहरण: जीएच === | ||
यादृच्छिक संचार जटिलता के एक और उदाहरण के लिए, हम [[गैप-हैमिंग समस्या|अंतर-हैमिंग समस्या]] (संक्षिप्त जीएच) के रूप में ज्ञात एक उदाहरण की ओर मुड़ते हैं। विधिवत रूप से, ऐलिस और बॉब दोनों बाइनरी संदेश, <math>x,y \in \{-1, +1\}^n</math> बनाए रखते हैं और यह निर्धारित करना चाहते हैं कि | यादृच्छिक संचार जटिलता के एक और उदाहरण के लिए, हम [[गैप-हैमिंग समस्या|अंतर-हैमिंग समस्या]] (संक्षिप्त जीएच) के रूप में ज्ञात एक उदाहरण की ओर मुड़ते हैं। विधिवत रूप से, ऐलिस और बॉब दोनों बाइनरी संदेश, <math>x,y \in \{-1, +1\}^n</math> बनाए रखते हैं और यह निर्धारित करना चाहते हैं कि स्ट्रिंग्स बहुत समान हैं या यदि वे बहुत समान नहीं हैं।विशेष रूप से, वे निम्नलिखित आंशिक बूलियन फलन की गणना करने के लिए यथासंभव कुछ बिट्स के संचरण की आवश्यकता वाले संचार प्रोटोकॉल को खोजना चाहेंगे, | ||
:<math> | :<math> | ||
| Line 193: | Line 193: | ||
:स्पष्ट रूप से, यदि प्रोटोकॉल नियतात्मक होना है, तो उन्हें अपने सभी बिट्स को संवाद करना होगा (यह इसलिए है, क्योंकि यदि कोई नियतात्मक, सख्त सूचकांकों का सबसमुच्चय है जो ऐलिस और बॉब एक दूसरे से रिले करते हैं, तो उस समुच्चय पर स्ट्रिंग्स की एक जोड़ी होने की कल्पना करें में असहमत <math>\sqrt{n} - 1</math> पदों। यदि किसी स्थिति में एक और असहमति उत्पन्न होती है जो रिलेटेड नहीं होती है, तो यह परिणाम को प्रभावित करती है <math> \text{GH}_n(x, y)</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> चुनता है और फिर साझा यादृच्छिक स्ट्रिंग के रूप में <math>r_i</math> का उपयोग करके P चलाता है। यह <math>r_i</math> की पसंद को संप्रेषित करने के लिए O(log 100n) = O(log n) बिट्स लेता है। | |||
आइए | आइए हम <math>p(x,y)</math> और <math>p'_R(x,y)</math> को प्रायिकता के रूप में परिभाषित करें कि <math>P</math> और <math>P'_R</math> निवेश <math>(x,y)</math> के लिए उचित मान की गणना करते हैं। | ||
एक निश्चित | एक निश्चित <math>(x,y)</math> के लिए, हम निम्नलिखित समीकरण प्राप्त करने के लिए होफ़डिंग की असमानता का उपयोग कर सकते हैं: | ||
:<math>\Pr_R[|p'_R(x,y) - p(x,y)| \geq 0.1] \leq 2 \exp(-2(0.1)^2 \cdot 100n) < 2^{-2n}</math> | :<math>\Pr_R[|p'_R(x,y) - p(x,y)| \geq 0.1] \leq 2 \exp(-2(0.1)^2 \cdot 100n) < 2^{-2n}</math> | ||
इस प्रकार जब हमारे निकट | इस प्रकार जब हमारे निकट <math>(x,y)</math> नियत नहीं है: | ||
:<math>\Pr_R[\exists (x,y):\, |p'_R(x,y) - p(x,y)| \geq 0.1] \leq \sum_{(x,y)} \Pr_R[|p'_R(x,y) - p(x,y)| \geq 0.1] < \sum_{(x,y)} 2^{-2n} = 1</math> | :<math>\Pr_R[\exists (x,y):\, |p'_R(x,y) - p(x,y)| \geq 0.1] \leq \sum_{(x,y)} \Pr_R[|p'_R(x,y) - p(x,y)| \geq 0.1] < \sum_{(x,y)} 2^{-2n} = 1</math> | ||
उपरोक्त अंतिम समानता धारण करती है क्योंकि | उपरोक्त अंतिम समानता धारण करती है क्योंकि <math>2^{2n}</math> अलग-अलग युग्म <math>(x,y)</math> हैं। चूंकि प्रायिकता 1 के बराबर नहीं है, इसलिए कुछ <math>R_0</math> है ताकि सभी <math>(x,y)</math> के लिए: | ||
:<math>|p'_{R_0}(x,y) - p(x,y)| < 0.1</math> | :<math>|p'_{R_0}(x,y) - p(x,y)| < 0.1</math> | ||
चूँकि <math>P</math> में अधिकतम 0.1 त्रुटि संभावना है, <math>P'_{R_0}</math> में अधिकतम 0.2 त्रुटि संभावना हो सकती है। | |||
== क्वांटम संचार जटिलता == | == क्वांटम संचार जटिलता == | ||
क्वांटम संचार जटिलता वितरित संगणना के समय क्वांटम प्रभावों का उपयोग करके संचार में कमी को संभव बनाने | क्वांटम संचार जटिलता वितरित संगणना के समय क्वांटम प्रभावों का उपयोग करके संचार में कमी को संभव बनाने का प्रयत्न करती है। | ||
संचार जटिलता के कम से कम तीन क्वांटम सामान्यीकरण प्रस्तावित किए गए हैं; सर्वेक्षण के लिए | संचार जटिलता के कम से कम तीन क्वांटम सामान्यीकरण प्रस्तावित किए गए हैं; सर्वेक्षण के लिए जी. ब्रैसर्ड द्वारा सुझाया गया पाठ देखें। | ||
पहला | पहला एक क्वेट-संचार मॉडल है, जहां पक्ष शास्त्रीय संचार के अतिरिक्त क्वांटम संचार का उपयोग कर सकती हैं, उदाहरण के लिए एक [[ प्रकाशित तंतु |प्रकाशित तंतु]] के माध्यम से फोटॉन का आदान-प्रदान करके। | ||
एक दूसरे मॉडल में संचार अभी भी शास्त्रीय बिट्स के साथ किया जाता है, | एक दूसरे मॉडल में संचार अभी भी शास्त्रीय बिट्स के साथ किया जाता है, परन्तु पक्षों को उनके प्रोटोकॉल के भाग के रूप में क्वांटम जटिलता अवस्थाओं की असीमित आपूर्ति में हेरफेर करने की अनुमति है। अपने जटिलता अवस्थाओं पर माप करके, पक्ष वितरित संगणना के समय शास्त्रीय संचार पर बचत कर सकती हैं। | ||
तीसरे मॉडल में [[qubit]] | तीसरे मॉडल में [[qubit|क्यूबिट]] संचार के अतिरिक्त पहले से साझा किए गए जटिलता तक पहुंच सम्मिलित है, और तीन क्वांटम मॉडल में सबसे कम खोजा गया है। | ||
== गैर-नियतात्मक संचार जटिलता == | == गैर-नियतात्मक संचार जटिलता == | ||
गैर-नियतात्मक संचार जटिलता में, ऐलिस और बॉब के निकट एक | गैर-नियतात्मक संचार जटिलता में, ऐलिस और बॉब के निकट एक भविष्यवाणी तक पहुंच है। भविष्यवाणी का शब्द प्राप्त करने के बाद, पक्ष <math>f(x,y)</math> निकालने के लिए संवाद करती हैं। गैर-नियतात्मक संचार जटिलता तब विनिमय किए गए बिट्स की संख्या और भविष्यवाणी शब्द की कोडन लंबाई के योग पर <math>(x,y)</math> पर अधिकतम होती है। | ||
अलग विधि से देखने पर, यह 0/1-आव्यूह की सभी 1-प्रविष्टियों को कॉम्बीनेटरियल 1-आयत (अर्थात, गैर-सन्निहित, गैर-उत्तल सबमैट्रिसेस द्वारा कवर करने के बराबर है, जिनकी प्रविष्टियाँ सभी एक हैं (कुशीलेविट्ज़ और निसान या डायट्ज़फेलबिंगर एट अल देखें। ))। गैर-नियतात्मक संचार जटिलता आव्यूह की संख्या को कवर करने वाले आयत का द्विआधारी लघुगणक है: किसी भी 0-प्रविष्टियों को कवर किए बिना, आव्यूह की सभी 1-प्रविष्टियों को कवर करने के लिए आवश्यक कॉम्बिनेटरियल 1-आयत की न्यूनतम संख्या। | अलग विधि से देखने पर, यह 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>(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> | ध्यान दें कि आवश्यकता है कि सिक्का व्यक्तिगत है आवश्यक है। विशेष रूप से, यदि ऐलिस और बॉब के बीच साझा किए गए सार्वजनिक बिट्स की संख्या को संचार जटिलता के विरुद्ध नहीं गिना जाता है, तो यह तर्क देना सरल है कि किसी भी कार्य की गणना करना <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|last=Sherstov|first=Alexander A.|date=October 2008|title=सममित कार्यों की असीमित-त्रुटि संचार जटिलता|journal=2008 49th Annual IEEE Symposium on Foundations of Computer Science|pages=384–393|doi=10.1109/focs.2008.20|isbn=978-0-7695-3436-7|s2cid=9072527}}</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> | फोरस्टर<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> | ||
Revision as of 09:03, 11 May 2023
सैद्धांतिक कंप्यूटर विज्ञान में, संचार जटिलता एक समस्या को हल करने के लिए आवश्यक संचार की मात्रा का अध्ययन करती है जब समस्या के निवेश को दो या दो से अधिक पक्षों के बीच संगणना वितरित किया जाता है। संचार जटिलता का अध्ययन पहली बार 1979 में एंड्रयू याओ द्वारा प्रस्तुत किया गया था, जब कई मशीनों के बीच गणना की समस्या का अध्ययन किया गया था।[1] समस्या को सामान्यतः निम्नानुसार कहा जाता है: दो पक्ष (परंपरागत रूप से ऐलिस और बॉब कहलाते हैं) प्रत्येक को एक (संभावित रूप से भिन्न) - अंश स्ट्रिंग और प्राप्त होता है। लक्ष्य ऐलिस के लिए एक निश्चित फलन के मान की गणना करना है, जो और दोनों पर निर्भर करता है, उनके बीच संचार की कम से कम मात्रा के साथ है।
जबकि ऐलिस और बॉब हमेशा ऐलिस को अपनी पूरी बिट स्ट्रिंग भेजकर सफल हो सकते हैं (जो तब फलन (गणित) की गणना करता है) ), यहाँ विचार बिट्स से कम संचार के साथ की गणना करने के चतुर विधि खोजने का है। ध्यान दें कि, संगणनात्मक जटिलता सिद्धांत के विपरीत, संचार जटिलता ऐलिस या बॉब द्वारा निष्पादित संगणनात्मक जटिलता या उपयोग की जाने वाली मेमोरी के आकार से संबंधित नहीं है, क्योंकि हम सामान्यतः ऐलिस या बॉब की संगणनात्मक शक्ति के विषय में कुछ भी नहीं मानते हैं।
दो पक्षों के साथ यह सार समस्या (जिसे दो-पक्षीय संचार जटिलता कहा जाता है), और बहुपक्षीय संचार जटिलता के साथ इसका सामान्य रूप, कई संदर्भों में प्रासंगिक है। वीएलएसआई परिपथ डिजाइन में, उदाहरण के लिए, एक वितरित संगणना के समय विभिन्न घटकों के बीच पारित विद्युत संकेतों की मात्रा को कम करके उपयोग की जाने वाली ऊर्जा को कम करना चाहता है। समस्या डेटा संरचनाओं के अध्ययन और कंप्यूटर नेटवर्क के अनुकूलन में भी प्रासंगिक है। क्षेत्र के सर्वेक्षणों के लिए, राव & येहुदयॉफ़ (2020) और कुशीलेविट्ज़ & निसान (2006) की पाठ्यपुस्तकें देखें।
विधिवत परिभाषा
आइए जहां हम विशिष्ट स्थिति में मानते हैं कि