संचार जटिलता

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

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

दो पक्षों के साथ यह सार समस्या (जिसे दो-पक्षीय संचार जटिलता कहा जाता है), और बहुपक्षीय संचार जटिलता के साथ इसका सामान्य रूप, कई संदर्भों में प्रासंगिक है। वीएलएसआई सर्किट डिजाइन में, उदाहरण के लिए, एक वितरित संगणना के दौरान विभिन्न घटकों के बीच पारित विद्युत संकेतों की मात्रा को कम करके उपयोग की जाने वाली ऊर्जा को कम करना चाहता है। समस्या डेटा संरचनाओं के अध्ययन और कंप्यूटर नेटवर्क के अनुकूलन में भी प्रासंगिक है। क्षेत्र के सर्वेक्षणों के लिए, द्वारा पाठ्यपुस्तकें देखें Rao & Yehudayoff (2020) और Kushilevitz & Nisan (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.