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

Latest revision as of 09:55, 17 May 2023

सैद्धांतिक कंप्यूटर विज्ञान में, संचार जटिलता एक समस्या को हल करने के लिए आवश्यक संचार की मात्रा का अध्ययन करती है जब समस्या के निवेश को दो या दो से अधिक पक्षों के बीच संगणना वितरित किया जाता है। संचार जटिलता का अध्ययन पहली बार 1979 में एंड्रयू याओ द्वारा प्रस्तुत किया गया था, जब कई मशीनों के बीच गणना की समस्या का अध्ययन किया गया था।^[1] समस्या को सामान्यतः निम्नानुसार कहा जाता है: दो पक्ष (परंपरागत रूप से ऐलिस और बॉब कहलाते हैं) प्रत्येक को एक (संभावित रूप से भिन्न) $n$ - अंश स्ट्रिंग $x$ और $y$ प्राप्त होता है। लक्ष्य ऐलिस के लिए एक निश्चित फलन $f(x,y)$ के मान की गणना करना है, जो $x$ और $y$ दोनों पर निर्भर करते है, उनके बीच संचार की कम से कम मात्रा के साथ है।

जबकि ऐलिस और बॉब हमेशा ऐलिस को अपनी पूरी $n$ बिट स्ट्रिंग भेजकर सफल हो सकते हैं (जो तब फलन (गणित) $f$ की गणना करता है)), यहाँ विचार $n$ बिट्स से कम संचार के साथ $f$ की गणना करने के चतुर विधि खोजने का है। ध्यान दें कि, संगणनात्मक जटिलता सिद्धांत के विपरीत, संचार जटिलता ऐलिस या बॉब द्वारा निष्पादित संगणनात्मक जटिलता या उपयोग की जाने वाली मेमोरी के आकार से संबंधित नहीं है, क्योंकि हम सामान्यतः ऐलिस या बॉब की संगणनात्मक शक्ति के विषय में कुछ भी नहीं मानते हैं।

दो पक्षों के साथ यह सार समस्या (जिसे दो-पक्षीय संचार जटिलता कहा जाता है), और बहुपक्षीय संचार जटिलता के साथ इसका सामान्य रूप, कई संदर्भों में प्रासंगिक है। वीएलएसआई परिपथ डिजाइन में, उदाहरण के लिए, वितरित संगणना के समय विभिन्न घटकों के बीच पारित विद्युत संकेतों की मात्रा को कम करके उपयोग की जाने वाली ऊर्जा को कम करना चाहता है। समस्या डेटा संरचनाओं के अध्ययन और कंप्यूटर नेटवर्क के अनुकूलन में भी प्रासंगिक है। क्षेत्र के सर्वेक्षणों के लिए, राव & येहुदयॉफ़ (2020) और कुशीलेविट्ज़ & निसान (2006) की पाठ्यपुस्तकें देखें।

विधिवत परिभाषा

आइए $f:X\times Y\rightarrow Z$ जहां हम विशिष्ट स्थिति में मानते हैं कि $X=Y=\{0,1\}^{n}$ और $Z=\{0,1\}$ । ऐलिसके निकट $n$ -बिट स्ट्रिंग $x\in X$ है जबकि बॉब के निकट $n$ -बिट स्ट्रिंग $y\in Y$ है। एक समय में एक दूसरे से संचार करके (कुछ संचार प्रोटोकॉल को अपनाते हुए जो पहले से सहमत हैं), ऐलिस और बॉब $f(x,y)$ के मान की गणना करना चाहते हैं जैसे कि कम से कम पक्ष संचार के अंत में मान जानता है। इस बिंदु पर उत्तर को वापस संप्रेषित किया जा सकता है ताकि अतिरिक्त बिट के मान पर दोनों पक्षों को उत्तर पता चल सके। कंप्यूटिंग $f$ की इस संचार समस्या का सबसे निकृष्‍ट स्थिति संचार जटिलता, जिसे $D(f)$ के रूप में दर्शाया गया है, को तब परिभाषित किया गया है

D(f)=

सबसे निकृष्‍ट स्थिति में ऐलिस और बॉब के बीच न्यूनतम बिट्स का आदान-प्रदान।

जैसा कि ऊपर देखा गया है, किसी भी फलन $f:\{0,1\}^{n}\times \{0,1\}^{n}\rightarrow \{0,1\}$ के लिए, अपने निकट $D(f)\leq n$ है। उपरोक्त परिभाषा का उपयोग करते हुए, फलन $f$ को आव्यूह $A$ (निवेश आव्यूह या संचार आव्यूह कहा जाता है) के रूप में सोचना उपयोगी होते है, जहां पंक्तियों को $x\in X$ और स्तंभों को $y\in Y$ द्वारा अनुक्रमित किया जाता है। आव्यूह की प्रविष्टियाँ $A_{x,y}=f(x,y)$ हैं। प्रारंभ में ऐलिस और बॉब दोनों के निकट संपूर्ण आव्यूह $A$ की एक प्रति है (यह मानते हुए कि फलन $f$ दोनों पक्षों को ज्ञात है)। फिर, फलन मान की गणना करने की समस्या को संबंधित आव्यूह प्रविष्टि पर शून्यीकरण-में के रूप में दोहराया जा सकता है। इस समस्या को हल किया जा सकता है यदि ऐलिस या बॉब $x$ और $y$ दोनों को जानते हैं। संचार की प्रारम्भ में, निवेश पर फलन के मान के लिए विकल्पों की संख्या आव्यूह का आकार, अर्थात $2^{2n}$ है। फिर, जब और जब प्रत्येक पक्ष दूसरे से थोड़ा संवाद करता है, तो उत्तर के लिए विकल्पों की संख्या कम हो जाती है क्योंकि यह पंक्तियों/स्तंभों के एक समुच्चय को समाप्त कर देते है जिसके परिणामस्वरूप $A$ का उपआव्यूह होता है।

अधिक विधिवत रूप से, एक समुच्चय $R\subseteq X\times Y$ को एक (सांयोगिक) आयत कहा जाता है यदि जब भी $(x_{1},y_{1})\in R$ और $(x_{2},y_{2})\in R$ तब $(x_{1},y_{2})\in R$ हो। समान रूप से, $R$ एक संयोजी आयत है यदि इसे कुछ $M\subseteq X$ और $N\subseteq Y$ के लिए $R=M\times N$ के रूप में व्यक्त किया जा सकता है। उस स्थिति पर विचार करें जब पक्षों के बीच $k$ बिट्स का पहले ही आदान-प्रदान हो चुका है। अब, विशेष के लिए $h\in \{0,1\}^{k}$ , आइए आव्यूह को परिभाषित करें

T_{h}=\{(x,y):{\text{ the }}k{\text{-bits exchanged on input }}(x,y){\text{ is }}h\}

फिर, $T_{h}\subseteq X\times Y$ , और यह दिखाना कठिन नहीं है कि $T_{h}$ $A$ में एक संयुक्त आयत है।

उदाहरण: $EQ$

हम उस स्थिति पर विचार करते हैं जहां ऐलिस और बॉब यह निर्धारित करने का प्रयास करते हैं कि उनके निवेश स्ट्रिंग्स बराबर हैं या नहीं। विधिवत रूप से, समानता फलन को परिभाषित करें, जिसे $EQ:\{0,1\}^{n}\times \{0,1\}^{n}\rightarrow \{0,1\}$ द्वारा दर्शाया गया है, $EQ(x,y)=1$ यदि $x=y$ है। जैसा कि हम नीचे प्रदर्शित करते हैं, $EQ$ को हल करने वाले किसी भी निर्धारक संचार प्रोटोकॉल को सबसे निकृष्‍ट स्थिति में संचार के $n$ बिट्स की आवश्यकता होती है। अनुकूलन उदाहरण के रूप में, $x,y\in \{0,1\}^{3}$ के साधारण स्थिति पर विचार करें। इस स्थिति में समानता फलन नीचे आव्यूह द्वारा दर्शाया जा सकता है। पंक्तियाँ $x$ की सभी संभावनाओं को $y$ के स्तंभों का प्रतिनिधित्व करती हैं।

ईक्यू	000	001	010	011	100	101	110	111
000	1	0	0	0	0	0	0	0
001	0	1	0	0	0	0	0	0
010	0	0	1	0	0	0	0	0
011	0	0	0	1	0	0	0	0
100	0	0	0	0	1	0	0	0
101	0	0	0	0	0	1	0	0
110	0	0	0	0	0	0	1	0
111	0	0	0	0	0	0	0	1

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

प्रमेय: $D(EQ)=n$

प्रमाण। मान लीजिए कि $D(EQ)\leq n-1$ । इसका अर्थ यह है कि वहाँ $x\neq x'$ स्थित है जैसे कि $(x,x)$ और $(x',x')$ में समान संचार प्रतिलेख $h$ है। चूंकि यह प्रतिलेख आयत को परिभाषित करता है, $f(x,x')$ भी 1 होना चाहिए। परिभाषा के अनुसार $x\neq x'$ और हम जानते हैं कि समानता मात्र $(a,b)$ के लिए सत्य है जब $a=b$ । यह एक निराकरण उत्पन्न करता है।

निर्धारक संचार निचली सीमाओं को सिद्ध करने की इस तकनीक को मूर्ख समुच्चय तकनीक कहा जाता है।^[2]

यादृच्छिक संचार जटिलता

उपरोक्त परिभाषा में, हम उन बिट्स की संख्या से संबंधित हैं जिन्हें निश्चित रूप से दो पक्षों के बीच प्रेषित किया जाना चाहिए। यदि दोनों पक्षों को एक यादृच्छिक संख्या जनक तक पहुंच प्रदान की जाती है, तो क्या वे बहुत कम सूचनाओं के आदान-प्रदान के साथ $f$ का मान निर्धारित कर सकते हैं? याओ, अपने सेमिनल पेपर में^[1] यादृच्छिक संचार जटिलता को परिभाषित करके इस प्रश्न का उत्तर देते हैं।

फलन $f$ के लिए यादृच्छिक प्रोटोकॉल $R$ में दो पक्षीय त्रुटि है।

\Pr[R(x,y)=0]>{\frac {2}{3}},{\textrm {if}}\,f(x,y)=0

\Pr[R(x,y)=1]>{\frac {2}{3}},{\textrm {if}}\,f(x,y)=1

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

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

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

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

उदाहरण: ईक्यू

ईक्यू के पिछले उदाहरण पर लौटते हुए, यदि निश्चितता की आवश्यकता नहीं है, ऐलिस और बॉब मात्र $O(\log n)$ संदेशों का उपयोग करके समानता की जाँच कर सकते हैं। निम्नलिखित प्रोटोकॉल पर विचार करें: मान लें कि ऐलिस और बॉब दोनों के निकट एक ही यादृच्छिक स्ट्रिंग $z\in \{0,1\}^{n}$ तक पहुंच है। ऐलिस $z\cdot x$ की गणना करता है और बॉब को यह बिट (इसे b कहते हैं) भेजता है। ( $(\cdot )$ GF (2) बिंदु उत्पाद है।) फिर बॉब b की तुलना $z\cdot y$ से करता है। यदि वे समान हैं, तो बॉब यह कहते हुए स्वीकार करते है कि x बराबर y है। नहीं तो वह मना कर देते है।

स्पष्ट रूप से, यदि $x=y$ , तो $z\cdot x=z\cdot y$ , इसलिए $Prob_{z}[Accept]=1$ । यदि x, y के बराबर नहीं है, तब भी यह संभव है कि $z\cdot x=z\cdot y$ , जो बॉब को अनुचित उत्तर देगा। यह कैसे होता है?

यदि x और y समान नहीं हैं, तो उन्हें कुछ स्थानों पर भिन्न होना चाहिए:

{\begin{cases}x=c_{1}c_{2}\ldots p\ldots p'\ldots x_{n}\\y=c_{1}c_{2}\ldots q\ldots q'\ldots y_{n}\\z=z_{1}z_{2}\ldots z_{i}\ldots z_{j}\ldots z_{n}\end{cases}}

जहाँ $x$ और $y$ सहमत होते हैं, $z_{i}*x_{i}=z_{i}*c_{i}=z_{i}*y_{i}$ इसलिए वे प्रतिबन्ध बिंदु उत्पादों को समान रूप से प्रभावित करती हैं। हम उन प्रतिबन्धों को सुरक्षित रूप से अनदेखा कर सकते हैं और मात्र वहीं देख सकते हैं $x$ और $y$ अलग होना। इसके अतिरिक्त, हम बिंदु उत्पादों के बराबर हैं या नहीं, इसे बदले बिना बिट्स $x_{i}$ और $y_{i}$ को विनिमय कर सकते हैं। इसका अर्थ है कि हम बिट्स को विनिमय कर सकते हैं ताकि $x$ में मात्र शून्य हो और $y$ में मात्र एक हो:

{\begin{cases}x'=00\ldots 0\\y'=11\ldots 1\\z'=z_{1}z_{2}\ldots z_{n'}\end{cases}}

ध्यान दें कि $z'\cdot x'=0$ और $z'\cdot y'=\Sigma _{i}z'_{i}$ । अब, प्रश्न बन जाता है: कुछ यादृच्छिक स्ट्रिंग $z'$ के लिए, क्या प्रायिकता है कि $\Sigma _{i}z'_{i}=0$ ? चूंकि प्रत्येक $z'_{i}$ की समान रूप से 0 या 1 होने की संभावना है, यह संभावना मात्र $1/2$ है। इस प्रकार, जब $x$ , $y$ , $Prob_{z}[Accept]=1/2$ के बराबर नहीं होते है। इसकी यथार्थता बढ़ाने के लिए एल्गोरिदम को कई बार दोहराया जा सकता है। यह एक यादृच्छिक संचार एल्गोरिदम के लिए आवश्यकताओं को पूरा करते है।

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

उदाहरण: जीएच

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

{\text{GH}}_{n}(x,y):={\begin{cases}-1&\langle x,y\rangle \leq {\sqrt {n}}\\+1&\langle x,y\rangle \geq {\sqrt {n}}.\end{cases}}

स्पष्ट रूप से, यदि प्रोटोकॉल नियतात्मक होना है, तो उन्हें अपने सभी बिट्स को संवाद करना होगा (यह इसलिए है, क्योंकि यदि कोई नियतात्मक, सख्त सूचकांकों का सबसमुच्चय है जो ऐलिस और बॉब एक दूसरे से रिले करते हैं, तो उस समुच्चय पर स्ट्रिंग्स की एक जोड़ी होने की कल्पना करें में असहमत

{\sqrt {n}}-1

पदों। यदि किसी स्थिति में एक और असहमति उत्पन्न होती है जो रिलेटेड नहीं होती है, तो यह परिणाम को प्रभावित करती है

{\text{GH}}_{n}(x,y)

, और इसलिए एक अनुचित प्रक्रिया का परिणाम होगा।

एक स्वाभाविक प्रश्न तब पूछा जाता है, यदि हमें $1/3$ समय की त्रुटि करने की अनुमति है (यादृच्छिक उदाहरणों पर $x,y$ समान रूप से $\{-1,+1\}^{n}$ ) से यादृच्छिक रूप से खींचा गया है, तो क्या हम कम बिट्स वाले प्रोटोकॉल से दूर हो सकते हैं? यह पता चला है कि 2012 में चक्रवर्ती और रेगेव के परिणाम के कारण उत्तर किंचित आश्चर्यजनक रूप से नहीं है: वे दिखाते हैं कि यादृच्छिक उदाहरणों के लिए, कोई भी प्रक्रिया जो कम से कम $2/3$ समय के लिए उचित है, संचार के $\Omega (n)$ बिट्स को भेजना चाहिए, जो अनिवार्य रूप से उन सभी को कहना है।

सार्वजनिक सिक्के बनाम व्यक्तिगत सिक्के

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

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

0.1 की अधिकतम त्रुटि दर के साथ कुछ यादृच्छिक प्रोटोकॉल P पर विचार करें। $R$ को लंबाई n के $100n$ स्ट्रिंग्स होने दें, क्रमांकित $r_{1},r_{2},\dots ,r_{100n}$ । इस प्रकार के $R$ को देखते हुए, एक नवीन प्रोटोकॉल $P'_{R}$ परिभाषित करें जो यादृच्छिक रूप से कुछ $r_{i}$ चुनता है और फिर साझा यादृच्छिक स्ट्रिंग के रूप में $r_{i}$ का उपयोग करके P चलाता है। यह $r_{i}$ की पसंद को संप्रेषित करने के लिए O (log 100n) = O (log n) बिट्स लेता है।

आइए हम $p(x,y)$ और $p'_{R}(x,y)$ को प्रायिकता के रूप में परिभाषित करें कि $P$ और $P'_{R}$ निवेश $(x,y)$ के लिए उचित मान की गणना करते हैं।

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

\Pr _{R}[|p'_{R}(x,y)-p(x,y)|\geq 0.1]\leq 2\exp(-2(0.1)^{2}\cdot 100n)<2^{-2n}

इस प्रकार जब हमारे निकट $(x,y)$ नियत नहीं है:

\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

उपरोक्त अंतिम समानता धारण करती है क्योंकि $2^{2n}$ अलग-अलग युग्म $(x,y)$ हैं। चूंकि प्रायिकता 1 के बराबर नहीं है, इसलिए कुछ $R_{0}$ है ताकि सभी $(x,y)$ के लिए:

|p'_{R_{0}}(x,y)-p(x,y)|<0.1

चूँकि $P$ में अधिकतम 0.1 त्रुटि संभावना है, $P'_{R_{0}}$ में अधिकतम 0.2 त्रुटि संभावना हो सकती है।

क्वांटम संचार जटिलता

क्वांटम संचार जटिलता वितरित संगणना के समय क्वांटम प्रभावों का उपयोग करके संचार में कमी को संभव बनाने का प्रयत्न करती है।

संचार जटिलता के कम से कम तीन क्वांटम सामान्यीकरण प्रस्तावित किए गए हैं; सर्वेक्षण के लिए जी. ब्रैसर्ड द्वारा सुझाया गया पाठ देखें।

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

एक दूसरे मॉडल में संचार अभी भी शास्त्रीय बिट्स के साथ किया जाता है, परन्तु पक्षों को उनके प्रोटोकॉल के भाग के रूप में क्वांटम जटिलता अवस्थाओं की असीमित आपूर्ति में हेरफेर करने की अनुमति है। अपने जटिलता अवस्थाओं पर माप करके, पक्ष वितरित संगणना के समय शास्त्रीय संचार पर बचत कर सकती हैं।

तीसरे मॉडल में क्यूबिट संचार के अतिरिक्त पहले से साझा किए गए जटिलता तक पहुंच सम्मिलित है, और तीन क्वांटम मॉडल में सबसे कम खोजा गया है।

गैर-नियतात्मक संचार जटिलता

गैर-नियतात्मक संचार जटिलता में, ऐलिस और बॉब के निकट एक भविष्यवाणी तक पहुंच है। भविष्यवाणी का शब्द प्राप्त करने के बाद, पक्ष $f(x,y)$ निकालने के लिए संवाद करती हैं। गैर-नियतात्मक संचार जटिलता तब विनिमय किए गए बिट्स की संख्या और भविष्यवाणी शब्द की कोडन लंबाई के योग पर $(x,y)$ पर अधिकतम होती है।

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

नियतात्मक संचार जटिलता के लिए कम सीमा प्राप्त करने के साधन के रूप में गैर-नियतात्मक संचार जटिलता उत्पन्न होती है (डाइट्ज़फेलबिंगर एट अल देखें), परन्तु गैर-ऋणात्मक आव्यूह के सिद्धांत में भी, जहां यह एक गैर-ऋणात्मक आव्यूह के गैर-ऋणात्मक पद (रैखिक बीजगणित) पर निचली सीमा देते है।।^[3]

असीमित-त्रुटि संचार जटिलता

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

ध्यान दें कि आवश्यकता है कि सिक्का व्यक्तिगत है आवश्यक है। विशेष रूप से, यदि ऐलिस और बॉब के बीच साझा किए गए सार्वजनिक बिट्स की संख्या को संचार जटिलता के विरुद्ध नहीं गिना जाता है, तो यह तर्क देना सरल है कि किसी भी फलन की गणना में $O(1)$ संचार जटिलता है।^[4] दूसरी ओर, दोनों मॉडल समान हैं यदि ऐलिस और बॉब द्वारा उपयोग किए जाने वाले सार्वजनिक बिट्स की संख्या को प्रोटोकॉल के कुल संचार के विरुद्ध गिना जाता है।^[5]

यद्यपि सूक्ष्म, इस मॉडल की निचली सीमाएं अत्यंत दृढ हैं। अधिक विशेष रूप से, यह स्पष्ट है कि इस वर्ग की समस्याओं पर कोई भी बाध्यता निश्चित रूप से नियतात्मक मॉडल और व्यक्तिगत और सार्वजनिक सिक्का मॉडल में समस्याओं पर समतुल्य सीमाएं लगाती है, परन्तु ऐसी सीमाएं गैर-नियतात्मक संचार मॉडल और क्वांटम संचार मॉडल के लिए भी तुरंत लागू होती हैं।^[6]

फोरस्टर^[7] इस वर्ग के लिए स्पष्ट निचली सीमा सिद्ध करने वाले पहले व्यक्ति थे, यह दिखाते हुए कि आंतरिक उत्पाद $\langle x,y\rangle$ की गणना के लिए संचार के कम से कम $\Omega (n)$ बिट्स की आवश्यकता होती है, यद्यपि एलोन, फ्रैंकल और रोडल के पहले के परिणाम ने सिद्ध कर दिया कि लगभग सभी बूलियन फलनों के लिए संचार जटिलता $f:\{0,1\}^{n}\times \{0,1\}^{n}\to \{0,1\}$ $\Omega (n)$ है।^[8]

विवृत समस्याएं

0 या 1 निवेश आव्यूह $M_{f}=[f(x,y)]_{x,y\in \{0,1\}^{n}}$ को ध्यान में रखते हुए, सबसे निकृष्‍ट स्थिति में निश्चित रूप से $f$ की गणना करने के लिए विनिमय किए गए बिट्स की न्यूनतम संख्या, $D(f)$ , आव्यूह $M_{f}$ के पद (रैखिक बीजगणित) के लघुगणक द्वारा नीचे से बाध्य होने के लिए जाना जाता है। लॉग पद अनुमान प्रस्ताव करता है कि संचार जटिलता, $D(f)$ , $M_{f}$ के पद के लघुगणक की निरंतर शक्ति से ऊपर से घिरा हुआ है। चूंकि D (f) लॉग पद $(M_{f})$ के बहुपदों द्वारा ऊपर और नीचे से घिरा हुआ है, हम कह सकते हैं कि D (f) लॉग पद $(M_{f})$ से बहुपद से संबंधित है। चूंकि आव्यूह का पद आव्यूह के आकार में गणना योग्य बहुपद समय है, इस प्रकार की ऊपरी सीमा आव्यूह की संचार जटिलता को बहुपद समय में अनुमानित करने की अनुमति देगी। यद्यपि, ध्यान दें कि आव्यूह का आकार ही निवेश के आकार में घातीय है।

यादृच्छिक प्रोटोकॉल के लिए, सबसे निकृष्‍ट स्थिति में विनिमय किए गए बिट्स की संख्या, r (f), बहुपद रूप से निम्न सूत्र से संबंधित होने का अनुमान लगाया गया था:

\log \min({\textrm {rank}}(M'_{f}):M'_{f}\in \mathbb {R} ^{2^{n}\times 2^{n}},(M_{f}-M'_{f})_{\infty }\leq 1/3).

ऐसे लॉग पद अनुमान बहुमानित हैं क्योंकि वे आव्यूह की संचार जटिलता के प्रश्न को आव्यूह के रैखिक रूप से स्वतंत्र पंक्तियों (स्तंभों) के प्रश्न तक कम कर देते हैं। लॉग-अनुमानित-पद अनुमान नामक इस विशेष संस्करण को वर्तमान में चट्टोपाध्याय, मंडे और शेरिफ (2019) द्वारा खंडन कर दिया गया था।^[9] आश्चर्यजनक रूप से सरल प्रति-उदाहरण का उपयोग करना। इससे पता चलता है कि संचार जटिलता समस्या का सार, उदाहरण के लिए उपरोक्त ईक्यू स्थिति में, यह पता लगाना है कि आव्यूह में निवेश जहाँ हैं, यह पता लगाने के लिए कि क्या वे समकक्ष हैं।

अनुप्रयोग

संचार जटिलता में निचली सीमा का उपयोग निर्णय ट्री जटिलता, वीएलएसआई परिपथ, डेटा संरचनाओं, अभिस्रवण एल्गोरिदम, ट्यूरिंग मशीनों के लिए समष्टि काल ट्रेडऑफ़ और अधिक में निचली सीमा को सिद्ध करने के लिए किया जा सकता है।^[2]

यह भी देखें

अंतर-हैमिंग की समस्या

↑ ^1.0 ^1.1 Yao, A. C. (1979), "Some Complexity Questions Related to Distributive Computing", Proc. Of 11th STOC, 14: 209–213
↑ ^2.0 ^2.1 Kushilevitz, Eyal; Nisan, Noam (1997). Communication Complexity. Cambridge University Press. ISBN 978-0-521-56067-2.
↑ Yannakakis, M. (1991). "रेखीय कार्यक्रमों द्वारा संयोजी इष्टतमीकरण समस्याओं को व्यक्त करना". J. Comput. Syst. Sci. 43 (3): 441–466. doi:10.1016/0022-0000(91)90024-y.
↑ Lovett, Shachar, CSE 291: Communication Complexity, Winter 2019 Unbounded-error protocols (PDF), retrieved June 9, 2019
↑ Göös, Mika; Pitassi, Toniann; Watson, Thomas (2018-06-01). "संचार जटिलता वर्गों का परिदृश्य". Computational Complexity. 27 (2): 245–304. doi:10.1007/s00037-018-0166-6. ISSN 1420-8954. S2CID 4333231.
↑ Sherstov, Alexander A. (October 2008). "सममित कार्यों की असीमित-त्रुटि संचार जटिलता". 2008 49th Annual IEEE Symposium on Foundations of Computer Science: 384–393. doi:10.1109/focs.2008.20. ISBN 978-0-7695-3436-7. S2CID 9072527.
↑ Forster, Jürgen (2002). "असीमित त्रुटि संभाव्य संचार जटिलता पर एक रैखिक निचली सीमा". Journal of Computer and System Sciences. 65 (4): 612–625. doi:10.1016/S0022-0000(02)00019-3.
↑ Alon, N.; Frankl, P.; Rodl, V. (October 1985). "सेट सिस्टम और संभाव्य संचार जटिलता का ज्यामितीय अहसास". 26th Annual Symposium on Foundations of Computer Science (SFCS 1985). Portland, OR, USA: IEEE: 277–280. CiteSeerX 10.1.1.300.9711. doi:10.1109/SFCS.1985.30. ISBN 9780818606441. S2CID 8416636.
↑ Chattopadhyay, Arkadev; Mande, Nikhil S.; Sherif, Suhail (2019). "The Log-Approximate-Rank Conjecture is False". 2019, Proceeding of the 51st Annual ACM Symposium on Theory of Computing: 42-53.https://doi.org/10.1145/3313276.3316353

संदर्भ

Rao, Anup; Yehudayoff, Amir (2020). Communication complexity and applications. Cambridge: Cambridge University Press. ISBN 9781108671644.
Kushilevitz, Eyal; Nisan, Noam (2006). Communication complexity. Cambridge: Cambridge University Press. ISBN 978-0-521-02983-4. OCLC 70764786.
Brassard, G। Quantum communication complexity: a survey। https://arxiv।org/abs/quant-ph/0101005
Dietzfelbinger, M।, J। Hromkovic, J।, and G। Schnitger, "A comparison of two lower-bound methods for communication complexity", Theoret। Comput। Sci। 168, 1996। 39-51।
Raz, Ran। "Circuit and Communication Complexity।" In Computational Complexity Theory। Steven Rudich and Avi Wigderson, eds। American Mathematical Society Institute for Advanced Study, 2004। 129-137।
A। C। Yao, "Some Complexity Questions Related to Distributed Computing", Proc। of 11th STOC, pp। 209–213, 1979। 14
I। Newman, Private vs। Common Random Bits in Communication Complexity, Information Processing Letters 39, 1991, pp। 67–71।

[yao1979-1] 1.0 ^1.1 Yao, A. C. (1979), "Some Complexity Questions Related to Distributive Computing", Proc. Of 11th STOC, 14: 209–213

[:0-2] 2.0 ^2.1 Kushilevitz, Eyal; Nisan, Noam (1997). Communication Complexity. Cambridge University Press. ISBN 978-0-521-56067-2.

[3] Yannakakis, M. (1991). "रेखीय कार्यक्रमों द्वारा संयोजी इष्टतमीकरण समस्याओं को व्यक्त करना". J. Comput. Syst. Sci. 43 (3): 441–466. doi:10.1016/0022-0000(91)90024-y.

[4] Lovett, Shachar, CSE 291: Communication Complexity, Winter 2019 Unbounded-error protocols (PDF), retrieved June 9, 2019

[5] Göös, Mika; Pitassi, Toniann; Watson, Thomas (2018-06-01). "संचार जटिलता वर्गों का परिदृश्य". Computational Complexity. 27 (2): 245–304. doi:10.1007/s00037-018-0166-6. ISSN 1420-8954. S2CID 4333231.

[6] Sherstov, Alexander A. (October 2008). "सममित कार्यों की असीमित-त्रुटि संचार जटिलता". 2008 49th Annual IEEE Symposium on Foundations of Computer Science: 384–393. doi:10.1109/focs.2008.20. ISBN 978-0-7695-3436-7. S2CID 9072527.

[7] Forster, Jürgen (2002). "असीमित त्रुटि संभाव्य संचार जटिलता पर एक रैखिक निचली सीमा". Journal of Computer and System Sciences. 65 (4): 612–625. doi:10.1016/S0022-0000(02)00019-3.

[8] Alon, N.; Frankl, P.; Rodl, V. (October 1985). "सेट सिस्टम और संभाव्य संचार जटिलता का ज्यामितीय अहसास". 26th Annual Symposium on Foundations of Computer Science (SFCS 1985). Portland, OR, USA: IEEE: 277–280. CiteSeerX 10.1.1.300.9711. doi:10.1109/SFCS.1985.30. ISBN 9780818606441. S2CID 8416636.

[9] Chattopadhyay, Arkadev; Mande, Nikhil S.; Sherif, Suhail (2019). "The Log-Approximate-Rank Conjecture is False". 2019, Proceeding of the 51st Annual ACM Symposium on Theory of Computing: 42-53.https://doi.org/10.1145/3313276.3316353

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

@@ Line 1: / Line 1: @@
 {{Short description|Complexity of sending information in a distributed algorithm}}
-[[सैद्धांतिक कंप्यूटर विज्ञान]] में, संचार जटिलता एक समस्या को हल करने के लिए आवश्यक संचार की मात्रा का अध्ययन करती है जब समस्या के निवेश को दो या दो से अधिक दलों के बीच संगणना वितरित किया जाता है। संचार जटिलता का अध्ययन पहली बार 1979 में [[एंड्रयू याओ]] द्वारा प्रस्तुत किया गया था, जब कई मशीनों के बीच गणना की समस्या का अध्ययन किया गया था।<ref name=yao1979>{{Citation
+[[सैद्धांतिक कंप्यूटर विज्ञान]] में, संचार जटिलता एक समस्या को हल करने के लिए आवश्यक संचार की मात्रा का अध्ययन करती है जब समस्या के निवेश को दो या दो से अधिक पक्षों के बीच संगणना वितरित किया जाता है। संचार जटिलता का अध्ययन पहली बार 1979 में [[एंड्रयू याओ]] द्वारा प्रस्तुत किया गया था, जब कई मशीनों के बीच गणना की समस्या का अध्ययन किया गया था।<ref name=yao1979>{{Citation
    | last = Yao
    | first = A. C.
@@ Line 8: / Line 8: @@
    | volume = 14
    | 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}} की पाठ्यपुस्तकें देखें।
+दो पक्षों के साथ यह सार समस्या (जिसे दो-पक्षीय संचार जटिलता कहा जाता है), और बहुपक्षीय संचार जटिलता के साथ इसका सामान्य रूप, कई संदर्भों में प्रासंगिक है। [[वीएलएसआई]] परिपथ डिजाइन में, उदाहरण के लिए, वितरित संगणना के समय विभिन्न घटकों के बीच पारित विद्युत संकेतों की मात्रा को कम करके उपयोग की जाने वाली ऊर्जा को कम करना चाहता है। समस्या डेटा संरचनाओं के अध्ययन और कंप्यूटर नेटवर्क के अनुकूलन में भी प्रासंगिक है। क्षेत्र के सर्वेक्षणों के लिए, {{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: 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>f: \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}</math>, अपने निकट <math>D(f) \leq n</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>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>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} \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 : \{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>।
+हम उस स्थिति पर विचार करते हैं जहां ऐलिस और बॉब यह निर्धारित करने का प्रयास करते हैं कि उनके निवेश स्ट्रिंग्स बराबर हैं या नहीं। विधिवत रूप से, समानता फलन को परिभाषित करें, जिसे <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;"
-! EQ
+! ईक्यू
 ! 000
 ! 001
@@ Line 124: / Line 123: @@
 |-
 |}
-जैसा कि आप देख सकते हैं, फलन केवल 1 का मानांकन करता है जब <math>x</math> के बराबर होती है <math>y</math> (यानी, विकर्ण पर)। यह देखना भी काफी आसान है कि कैसे एक बिट संचार आपकी संभावनाओं को आधे में विभाजित करता है। यदि आप जानते हैं कि का पहला बिट <math>y</math> 1 है, तो आपको केवल आधे स्तंभों पर विचार करना होगा (जहाँ <math>y</math> 100, 101, 110 या 111 के बराबर हो सकता है)।
+जैसा कि आप देख सकते हैं, फलन मात्र 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) \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>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
 | last2=Nisan | first2=Noam  | author-link2=Noam Nisan
 | title=Communication Complexity
@@ Line 140: / Line 139: @@
 == यादृच्छिक संचार जटिलता ==
-उपरोक्त परिभाषा में, हम उन बिट्स की संख्या से संबंधित हैं जिन्हें निश्चित रूप से दो पक्षों के बीच प्रेषित किया जाना चाहिए। यदि दोनों पक्षों को एक यादृच्छिक संख्या जनरेटर तक पहुंच दी जाती है, तो क्या वे इसका मान निर्धारित कर सकते हैं <math>f</math> बहुत कम सूचनाओं के आदान-प्रदान के साथ? याओ, अपने सेमिनल पेपर में<ref name=yao1979/>यादृच्छिक संचार जटिलता को परिभाषित करके इस प्रश्न का उत्तर दें।
+उपरोक्त परिभाषा में, हम उन बिट्स की संख्या से संबंधित हैं जिन्हें निश्चित रूप से दो पक्षों के बीच प्रेषित किया जाना चाहिए। यदि दोनों पक्षों को एक यादृच्छिक संख्या जनक तक पहुंच प्रदान की जाती है, तो क्या वे बहुत कम सूचनाओं के आदान-प्रदान के साथ <math>f</math> का मान निर्धारित कर सकते हैं? याओ, अपने सेमिनल पेपर में<ref name=yao1979/> यादृच्छिक संचार जटिलता को परिभाषित करके इस प्रश्न का उत्तर देते हैं।
-एक यादृच्छिक प्रोटोकॉल <math>R</math> एक समारोह के लिए <math>f</math> दो तरफा त्रुटि है।
+फलन <math>f</math> के लिए यादृच्छिक प्रोटोकॉल <math>R</math> में दो पक्षीय त्रुटि है।
 :<math>
@@ Line 150: / Line 149: @@
 \Pr[R(x,y) = 1] > \frac{2}{3}, \textrm{if }\, f(x,y) = 1
 </math>
-एक यादृच्छिक प्रोटोकॉल एक नियतात्मक प्रोटोकॉल है जो अपने सामान्य निवेश के अतिरिक्त एक अतिरिक्त यादृच्छिक स्ट्रिंग का उपयोग करता है। इसके लिए दो मॉडल हैं: एक सार्वजनिक स्ट्रिंग एक यादृच्छिक स्ट्रिंग है जिसे दोनों पक्षों द्वारा पहले से जाना जाता है, जबकि एक निजी स्ट्रिंग एक पार्टी द्वारा उत्पन्न की जाती है और इसे दूसरे पक्ष को सूचित किया जाना चाहिए। नीचे प्रस्तुत एक प्रमेय से पता चलता है कि किसी भी सार्वजनिक स्ट्रिंग प्रोटोकॉल को एक निजी स्ट्रिंग प्रोटोकॉल द्वारा अनुकरण किया जा सकता है जो मूल की तुलना में O(log n) अतिरिक्त बिट्स का उपयोग करता है।
+एक यादृच्छिक प्रोटोकॉल नियतात्मक प्रोटोकॉल है जो अपने सामान्य निवेश के अतिरिक्त एक अतिरिक्त यादृच्छिक स्ट्रिंग का उपयोग करता है। इसके लिए दो मॉडल हैं: सार्वजनिक स्ट्रिंग एक यादृच्छिक स्ट्रिंग है जिसे दोनों पक्षों द्वारा पहले से जाना जाता है, जबकि व्यक्तिगत स्ट्रिंग पक्ष द्वारा उत्पन्न की जाती है और इसे दूसरे पक्ष को सूचित किया जाना चाहिए। नीचे प्रस्तुत प्रमेय से पता चलता है कि किसी भी सार्वजनिक स्ट्रिंग प्रोटोकॉल को व्यक्तिगत स्ट्रिंग प्रोटोकॉल द्वारा अनुकरण किया जा सकता है जो मूल की तुलना में O (log n) अतिरिक्त बिट्स का उपयोग करता है।
-ध्यान दें कि उपरोक्त प्रायिकता असमानताओं में, प्रोटोकॉल के परिणाम को केवल यादृच्छिक स्ट्रिंग पर निर्भर समझा जाता है; दोनों तार x और y स्थिर रहते हैं। दूसरे शब्दों में, यदि यादृच्छिक स्ट्रिंग आर का उपयोग करते समय आर (एक्स, वाई) जी (एक्स, वाई, आर) उत्पन्न करता है, तो जी (एक्स, वाई, आर) = एफ (एक्स, वाई) कम से कम 2/3 के लिए स्ट्रिंग आर के लिए विकल्प।
+ध्यान दें कि उपरोक्त प्रायिकता असमानताओं में, प्रोटोकॉल के परिणाम को मात्र यादृच्छिक स्ट्रिंग पर निर्भर समझा जाता है; दोनों स्ट्रिंग्स x और y स्थिर रहते हैं। दूसरे शब्दों में, यदि यादृच्छिक स्ट्रिंग r का उपयोग करते समय r (x, y) g (x, y, r) उत्पन्न करते है, फिर g (x, y, r) = f (x, y) स्ट्रिंग r के लिए सभी विकल्पों में से कम से कम 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 है। नहीं तो वह मना कर देता है।
+ईक्यू के पिछले उदाहरण पर लौटते हुए, यदि निश्चितता की आवश्यकता नहीं है, ऐलिस और बॉब मात्र {{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>, जो बॉब को गलत उत्तर देगा। यह कैसे होता है?
+स्पष्ट रूप से, यदि <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 समान नहीं हैं, तो उन्हें कुछ स्थानों पर भिन्न होना चाहिए:
@@ Line 171: / Line 170: @@
 z = z_1 z_2 \ldots z_i \ldots z_j \ldots z_n
 \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}} में केवल एक ही शामिल है:
+जहाँ {{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}
@@ Line 178: / Line 177: @@
 z' = z_1 z_2 \ldots z_{n'}
 \end{cases}</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> होने की समान संभावना है {{val|0}} या {{val|1}}, यह संभावना न्यायसंगत है <math>1/2</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> की समान रूप से 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 की एक यादृच्छिक स्ट्रिंग साझा करते हैं, तो वे गणना करने के लिए एक दूसरे को एक बिट भेज सकते हैं <math>EQ(x,y)</math>। अगले भाग में, यह दिखाया गया है कि ऐलिस और बॉब केवल विनिमय कर सकते हैं {{tmath|O(\log n)}} बिट्स जो लंबाई n की एक यादृच्छिक स्ट्रिंग साझा करने के समान हैं। एक बार जो दिखाया गया है, यह इस प्रकार है कि EQ की गणना की जा सकती है {{tmath|O(\log 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>x,y \in \{-1, +1\}^n</math> बनाए रखते हैं और यह निर्धारित करना चाहते हैं कि स्ट्रिंग्स बहुत समान हैं या यदि वे बहुत समान नहीं हैं।विशेष रूप से, वे निम्नलिखित आंशिक बूलियन फलन की गणना करने के लिए यथासंभव कुछ बिट्स के संचरण की आवश्यकता वाले संचार प्रोटोकॉल को खोजना चाहेंगे,
 :<math>
@@ Line 192: / Line 190: @@
 +1 & \langle x, y \rangle \geq \sqrt{n}.
 \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> संचार के लायक बिट्स, जो अनिवार्य रूप से उन सभी को कहना है।
+एक स्वाभाविक प्रश्न तब पूछा जाता है, यदि हमें <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) बिट्स का उपयोग करता है।
-सहज रूप से, हम स्ट्रिंग्स के कुछ सेट पा सकते हैं जिनमें त्रुटि में केवल थोड़ी सी वृद्धि के साथ यादृच्छिक प्रोटोकॉल को चलाने के लिए पर्याप्त यादृच्छिकता है। इस सेट को पहले से साझा किया जा सकता है, और एक यादृच्छिक स्ट्रिंग को चित्रित करने के बजाय, ऐलिस और बॉब को केवल इस बात पर सहमत होना चाहिए कि साझा सेट से किस स्ट्रिंग को चुनना है। यह सेट इतना छोटा है कि पसंद को कुशलता से संप्रेषित किया जा सकता है। एक औपचारिक प्रमाण इस प्रकार है।
+सहज रूप से, हम स्ट्रिंग्स के कुछ समुच्चय पा सकते हैं जिनमें त्रुटि में मात्र थोड़ी सी वृद्धि के साथ यादृच्छिक प्रोटोकॉल को चलाने के लिए पर्याप्त यादृच्छिकता है। इस समुच्चय को पहले से साझा किया जा सकता है, और यादृच्छिक स्ट्रिंग को चित्रित करने के अतिरिक्त, ऐलिस और बॉब को मात्र इस बात पर सहमत होना चाहिए कि साझा समुच्चय से किस स्ट्रिंग को चुनना है। यह समुच्चय इतना छोटा है कि पसंद को कुशलता से संप्रेषित किया जा सकता है। एक विधिवत प्रमाण इस प्रकार है।
-।1 की अधिकतम त्रुटि दर के साथ कुछ यादृच्छिक प्रोटोकॉल P पर विचार करें। होने देना <math>R</math> होना <math>100n</math> लंबाई एन के तार, क्रमांकित <math>r_1, r_2, \dots, r_{100n}</math>। ऐसा दिया <math>R</math>, एक नया प्रोटोकॉल परिभाषित करें <math>P'_R</math> जो बेतरतीब ढंग से कुछ चुनता है <math>r_i</math> और फिर P का उपयोग करके चलाता है <math>r_i</math> साझा यादृच्छिक स्ट्रिंग के रूप में। पसंद के विषय में बताने के लिए O(log 100n) = O(log n) बिट्स लगते हैं <math>r_i</math>।
+.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>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>(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>(x,y)</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>2^{2n}</math> अलग जोड़े <math>(x,y)</math>। चूंकि प्रायिकता 1 के बराबर नहीं है, इसलिए कुछ है <math>R_0</math> ताकि सभी के लिए <math>(x,y)</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</math> अधिकतम 0।1 त्रुटि संभावना है, <math>P'_{R_0}</math> अधिकतम 0।2 त्रुटि संभावना हो सकती है।
+चूँकि <math>P</math> में अधिकतम 0.1 त्रुटि संभावना है, <math>P'_{R_0}</math> में अधिकतम 0.2 त्रुटि संभावना हो सकती है।
 == क्वांटम संचार जटिलता ==
-क्वांटम संचार जटिलता वितरित संगणना के समय क्वांटम प्रभावों का उपयोग करके संचार में कमी को संभव बनाने की कोशिश करती है।
+क्वांटम संचार जटिलता वितरित संगणना के समय क्वांटम प्रभावों का उपयोग करके संचार में कमी को संभव बनाने का प्रयत्न करती है।
-संचार जटिलता के कम से कम तीन क्वांटम सामान्यीकरण प्रस्तावित किए गए हैं; सर्वेक्षण के लिए जी। ब्रैसर्ड द्वारा सुझाया गया पाठ देखें।
+संचार जटिलता के कम से कम तीन क्वांटम सामान्यीकरण प्रस्तावित किए गए हैं; सर्वेक्षण के लिए जी. ब्रैसर्ड द्वारा सुझाया गया पाठ देखें।
-पहला है क्वांटम उलझाव | क्वेट-कम्युनिकेशन मॉडल, जहां पार्टियां शास्त्रीय संचार के बजाय क्वांटम संचार का उपयोग कर सकती हैं, उदाहरण के लिए एक [[ प्रकाशित तंतु |प्रकाशित तंतु]] के माध्यम से फोटॉन का आदान-प्रदान करके।
+पहला एक क्वेट-संचार मॉडल है, जहां पक्ष शास्त्रीय संचार के अतिरिक्त क्वांटम संचार का उपयोग कर सकती हैं, उदाहरण के लिए [[ प्रकाशित तंतु |प्रकाशित तंतु]] के माध्यम से फोटॉन का आदान-प्रदान करके।
-एक दूसरे मॉडल में संचार अभी भी शास्त्रीय बिट्स के साथ किया जाता है, लेकिन दलों को उनके प्रोटोकॉल के हिस्से के रूप में क्वांटम उलझन वाले राज्यों की असीमित आपूर्ति में हेरफेर करने की अनुमति है। अपने उलझे हुए राज्यों पर माप करके, पार्टियां वितरित संगणना के समय शास्त्रीय संचार पर बचत कर सकती हैं।
+एक दूसरे मॉडल में संचार अभी भी शास्त्रीय बिट्स के साथ किया जाता है, परन्तु पक्षों को उनके प्रोटोकॉल के भाग के रूप में क्वांटम जटिलता अवस्थाओं की असीमित आपूर्ति में हेरफेर करने की अनुमति है। अपने जटिलता अवस्थाओं पर माप करके, पक्ष वितरित संगणना के समय शास्त्रीय संचार पर बचत कर सकती हैं।
-तीसरे मॉडल में [[qubit]] कम्युनिकेशन के अलावा पहले से साझा किए गए उलझाव तक पहुंच शामिल है, और तीन क्वांटम मॉडल में सबसे कम खोजा गया है।
+तीसरे मॉडल में [[qubit|क्यूबिट]] संचार के अतिरिक्त पहले से साझा किए गए जटिलता तक पहुंच सम्मिलित है, और तीन क्वांटम मॉडल में सबसे कम खोजा गया है।
 == गैर-नियतात्मक संचार जटिलता ==
-गैर-नियतात्मक संचार जटिलता में, ऐलिस और बॉब के निकट एक ऑरेकल तक पहुंच है। दैवज्ञ का वचन प्राप्त करने के बाद, पक्ष निष्कर्ष निकालने के लिए संवाद करते हैं <math>f(x,y)</math>। गैर-नियतात्मक संचार जटिलता तब सभी जोड़ियों में अधिकतम होती है <math>(x,y)</math> एक्सचेंज किए गए बिट्स की संख्या और ऑरेकल शब्द की कोडिंग लंबाई के योग पर।
+गैर-नियतात्मक संचार जटिलता में, ऐलिस और बॉब के निकट एक भविष्यवाणी तक पहुंच है। भविष्यवाणी का शब्द प्राप्त करने के बाद, पक्ष <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>
+नियतात्मक संचार जटिलता के लिए कम सीमा प्राप्त करने के साधन के रूप में गैर-नियतात्मक संचार जटिलता उत्पन्न होती है (डाइट्ज़फेलबिंगर एट अल देखें), परन्तु गैर-ऋणात्मक आव्यूह के सिद्धांत में भी, जहां यह एक गैर-ऋणात्मक आव्यूह के [[गैर-नकारात्मक रैंक (रैखिक बीजगणित)|गैर-ऋणात्मक पद (रैखिक बीजगणित]]) पर निचली सीमा देते है।।<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>(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|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>
-या 1 निवेश मैट्रिक्स को ध्यान में रखते हुए <math>M_f=[f(x,y)]_{x,y\in \{0,1\}^n}</math>गणना करने के लिए एक्सचेंज किए गए बिट्स की न्यूनतम संख्या <math>f</math> निश्चित रूप से सबसे निकृष्‍ट स्थिति में, <math>D(f)</math>, मैट्रिक्स के [[रैंक (रैखिक बीजगणित)]] के लघुगणक द्वारा नीचे से घिरा हुआ जाना जाता है <math>M_f</math>। लॉग रैंक अनुमान प्रस्ताव करता है कि संचार जटिलता, <math>D(f)</math>, के रैंक के लघुगणक की एक निरंतर शक्ति से ऊपर से घिरा हुआ है <math>M_f</math>। चूंकि डी (एफ) लॉग रैंक के बहुपदों द्वारा ऊपर और नीचे से घिरा हुआ है<math>(M_f)</math>, हम कह सकते हैं कि डी (एफ) लॉग रैंक से बहुपद से संबंधित है<math>(M_f)</math>। चूंकि मैट्रिक्स का रैंक मैट्रिक्स के आकार में गणना योग्य बहुपद समय है, इस तरह की ऊपरी सीमा मैट्रिक्स की संचार जटिलता को बहुपद समय में अनुमानित करने की अनुमति देगी। हालाँकि, ध्यान दें कि मैट्रिक्स का आकार ही निवेश के आकार में घातीय है।
-एक यादृच्छिक प्रोटोकॉल के लिए, सबसे निकृष्‍ट स्थिति में एक्सचेंज किए गए बिट्स की संख्या, आर (एफ), बहुपद रूप से निम्न सूत्र से संबंधित होने का अनुमान लगाया गया था:
+== विवृत समस्याएं ==
+या 1 निवेश आव्यूह <math>M_f=[f(x,y)]_{x,y\in \{0,1\}^n}</math> को ध्यान में रखते हुए, सबसे निकृष्‍ट स्थिति में निश्चित रूप से <math>f</math> की गणना करने के लिए विनिमय किए गए बिट्स की न्यूनतम संख्या, <math>D(f)</math>, आव्यूह <math>M_f</math> के [[रैंक (रैखिक बीजगणित)|पद (रैखिक बीजगणित]]) के लघुगणक द्वारा नीचे से बाध्य होने के लिए जाना जाता है। लॉग पद अनुमान प्रस्ताव करता है कि संचार जटिलता, <math>D(f)</math>, <math>M_f</math> के पद के लघुगणक की निरंतर शक्ति से ऊपर से घिरा हुआ है। चूंकि '''''D (f''''') लॉग पद <math>(M_f)</math> के बहुपदों द्वारा ऊपर और नीचे से घिरा हुआ है, हम कह सकते हैं कि '''''D (f''''') लॉग पद <math>(M_f)</math> से बहुपद से संबंधित है। चूंकि आव्यूह का पद आव्यूह के आकार में गणना योग्य बहुपद समय है, इस प्रकार की ऊपरी सीमा आव्यूह की संचार जटिलता को बहुपद समय में अनुमानित करने की अनुमति देगी। यद्यपि, ध्यान दें कि आव्यूह का आकार ही निवेश के आकार में घातीय है।
+यादृच्छिक प्रोटोकॉल के लिए, सबसे निकृष्‍ट स्थिति में विनिमय किए गए बिट्स की संख्या, '''''r (f'''''), बहुपद रूप से निम्न सूत्र से संबंधित होने का अनुमान लगाया गया था:
 : <math>\log \min(\textrm{rank}(M'_f): M'_f\in \mathbb{R}^{2^n\times 2^n}, (M_f - M'_f)_\infty\leq 1/3).</math>
-ऐसे लॉग रैंक अनुमान मानवान हैं क्योंकि वे मैट्रिक्स की संचार जटिलता के प्रश्न को मैट्रिक्स के रैखिक रूप से स्वतंत्र पंक्तियों (स्तंभों) के प्रश्न तक कम कर देते हैं। लॉग-अनुमानित-रैंक अनुमान नामक इस विशेष संस्करण को हाल ही में चट्टोपाध्याय, मंडे और शेरिफ (2019) द्वारा खारिज कर दिया गया था।<ref>Chattopadhyay, Arkadev; Mande, Nikhil S.; Sherif, Suhail (2019). "The Log-Approximate-Rank Conjecture is False". 2019, Proceeding of the 51st Annual ACM Symposium on Theory of Computing: 42-53.https://doi.org/10.1145/3313276.3316353</ref> आश्चर्यजनक रूप से सरल प्रति-उदाहरण का उपयोग करना। इससे पता चलता है कि संचार जटिलता समस्या का सार, उदाहरण के लिए उपरोक्त EQ स्थिति में, यह पता लगाना है कि मैट्रिक्स में निवेश कहाँ हैं, यह पता लगाने के लिए कि क्या वे समकक्ष हैं।
+ऐसे लॉग पद अनुमान बहुमानित हैं क्योंकि वे आव्यूह की संचार जटिलता के प्रश्न को आव्यूह के रैखिक रूप से स्वतंत्र पंक्तियों (स्तंभों) के प्रश्न तक कम कर देते हैं। लॉग-अनुमानित-पद अनुमान नामक इस विशेष संस्करण को वर्तमान में चट्टोपाध्याय, मंडे और शेरिफ (2019) द्वारा खंडन कर दिया गया था।<ref>Chattopadhyay, Arkadev; Mande, Nikhil S.; Sherif, Suhail (2019). "The Log-Approximate-Rank Conjecture is False". 2019, Proceeding of the 51st Annual ACM Symposium on Theory of Computing: 42-53.https://doi.org/10.1145/3313276.3316353</ref> आश्चर्यजनक रूप से सरल प्रति-उदाहरण का उपयोग करना। इससे पता चलता है कि संचार जटिलता समस्या का सार, उदाहरण के लिए उपरोक्त ईक्यू स्थिति में, यह पता लगाना है कि आव्यूह में निवेश जहाँ हैं, यह पता लगाने के लिए कि क्या वे समकक्ष हैं।
 == अनुप्रयोग ==
-संचार जटिलता में निचली सीमा का उपयोग निर्णय ट्री जटिलता, [[वीएलएसआई सर्किट|वीएलएसआई परिपथ]], डेटा संरचनाओं, [[स्ट्रीमिंग एल्गोरिदम]], ट्यूरिंग मशीनों के लिए स्पेस-टाइम ट्रेडऑफ़ और अधिक में निचली सीमा को साबित करने के लिए किया जा सकता है।<ref name=":0" />
+संचार जटिलता में निचली सीमा का उपयोग निर्णय ट्री जटिलता, [[वीएलएसआई सर्किट|वीएलएसआई परिपथ]], डेटा संरचनाओं, [[स्ट्रीमिंग एल्गोरिदम|अभिस्रवण एल्गोरिदम]], ट्यूरिंग मशीनों के लिए समष्टि काल ट्रेडऑफ़ और अधिक में निचली सीमा को सिद्ध करने के लिए किया जा सकता है।<ref name=":0" />
 == यह भी देखें ==
-* गैप-हैमिंग की समस्या
+* अंतर-हैमिंग की समस्या
 == टिप्पणियाँ ==
@@ Line 277: / Line 279: @@
 * I। Newman, [http://u.cs.biu.ac.il/~zarosih/70/files/private_vs__common_random_bits_in_commun_493418.pdf Private vs। Common Random Bits in Communication Complexity], Information Processing Letters 39, 1991, pp।&nbsp;67–71।
-{{DEFAULTSORT:Communication Complexity}}[[Category: सूचना सिद्धांत]] [[Category: कम्प्यूटेशनल जटिलता सिद्धांत]] [[Category: क्वांटम जटिलता सिद्धांत]]
+{{DEFAULTSORT:Communication Complexity}}
-[[Category: Machine Translated Page]]
+[[Category:Created On 07/05/2023|Communication Complexity]]
-[[Category:Created On 07/05/2023]]
+[[Category:Lua-based templates|Communication Complexity]]
+[[Category:Machine Translated Page|Communication Complexity]]
+[[Category:Pages with script errors|Communication Complexity]]
+[[Category:Templates Vigyan Ready|Communication Complexity]]
+[[Category:Templates that add a tracking category|Communication Complexity]]
+[[Category:Templates that generate short descriptions|Communication Complexity]]
+[[Category:Templates using TemplateData|Communication Complexity]]
+[[Category:कम्प्यूटेशनल जटिलता सिद्धांत|Communication Complexity]]
+[[Category:क्वांटम जटिलता सिद्धांत|Communication Complexity]]
+[[Category:सूचना सिद्धांत|Communication Complexity]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 09:55, 17 May 2023

Contents