संचार जटिलता

सैद्धांतिक कंप्यूटर विज्ञान में, संचार जटिलता एक समस्या को हल करने के लिए आवश्यक संचार की मात्रा का अध्ययन करती है जब समस्या के निवेश को दो या दो से अधिक दलों के बीच संगणना वितरित किया जाता है। संचार जटिलता का अध्ययन पहली बार 1979 में एंड्रयू याओ द्वारा प्रस्तुत किया गया था, जब कई मशीनों के बीच गणना की समस्या का अध्ययन किया गया था। समस्या को सामान्यतः निम्नानुसार कहा जाता है: दो पक्ष (परंपरागत रूप से ऐलिस और बॉब कहलाते हैं) प्रत्येक को एक (संभावित रूप से भिन्न) $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$ को एक (combinatorial) आयत कहा जाता है यदि जब भी $(x_{1},y_{1})\in R$ और $(x_{2},y_{2})\in R$ तब $(x_{1},y_{2})\in R$ हो। समान रूप से, $R$ एक संयोजी आयत है यदि इसे व्यक्त किया जा सकता है $R=M\times N$ कुछ के लिए $M\subseteq X$ और $N\subseteq Y$। स्थिति पर विचार करें जब $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$।

EQ	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$। यह एक विरोधाभास पैदा करता है।

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

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

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

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

$\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 स्थिर रहते हैं। दूसरे शब्दों में, यदि यादृच्छिक स्ट्रिंग आर का उपयोग करते समय आर (एक्स, वाई) जी (एक्स, वाई, आर) उत्पन्न करता है, तो जी (एक्स, वाई, आर) = एफ (एक्स, वाई) कम से कम 2/3 के लिए स्ट्रिंग आर के लिए विकल्प।

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

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

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

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

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

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

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

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

आइए परिभाषित करते हैं $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 त्रुटि संभावना हो सकती है।

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

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

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

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

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

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

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

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

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

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

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

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

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

खुली समस्याएं

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

अनुप्रयोग

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

यह भी देखें

• गैप-हैमिंग की समस्या

संदर्भ

• 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।