संचार जटिलता

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

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

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

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

अनुप्रयोग

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

यह भी देखें

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

संदर्भ

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