संचार जटिलता

सैद्धांतिक कंप्यूटर विज्ञान में, संचार जटिलता एक समस्या को हल करने के लिए आवश्यक संचार की मात्रा का अध्ययन करती है जब समस्या के निवेश को दो या दो से अधिक पक्षों के बीच संगणना वितरित किया जाता है। संचार जटिलता का अध्ययन पहली बार 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$ को एक (सांयोगिक) आयत कहा जाता है यदि जब भी $(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$। यह एक निराकरण उत्पन्न करता है।

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

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

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

फलन $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$ और बॉब को यह बिट (इसे बी कहते हैं) भेजता है। ( $(\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 की एक यादृच्छिक स्ट्रिंग साझा करने के समान हैं। एक बार जो दिखाया गया है, यह इस प्रकार है कि ईक्यू की गणना की जा सकती है $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}$। चूंकि डी (f) लॉग रैंक के बहुपदों द्वारा ऊपर और नीचे से घिरा हुआ है$(M_{f})$, हम कह सकते हैं कि डी (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) द्वारा खारिज कर दिया गया था। आश्चर्यजनक रूप से सरल प्रति-उदाहरण का उपयोग करना। इससे पता चलता है कि संचार जटिलता समस्या का सार, उदाहरण के लिए उपरोक्त ईक्यू स्थिति में, यह पता लगाना है कि आव्यूह में निवेश कहाँ हैं, यह पता लगाने के लिए कि क्या वे समकक्ष हैं।

अनुप्रयोग

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

यह भी देखें

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

संदर्भ

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