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

Revision as of 09:03, 11 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}$ । चूंकि डी (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) द्वारा खारिज कर दिया गया था।^[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 29: / Line 29: @@
 === उदाहरण: <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;"
@@ Line 151: / Line 151: @@
 एक यादृच्छिक प्रोटोकॉल एक नियतात्मक प्रोटोकॉल है जो अपने सामान्य निवेश के अतिरिक्त एक अतिरिक्त यादृच्छिक स्ट्रिंग का उपयोग करता है। इसके लिए दो मॉडल हैं: एक सार्वजनिक स्ट्रिंग एक यादृच्छिक स्ट्रिंग है जिसे दोनों पक्षों द्वारा पहले से जाना जाता है, जबकि एक व्यक्तिगत स्ट्रिंग एक पक्ष द्वारा उत्पन्न की जाती है और इसे दूसरे पक्ष को सूचित किया जाना चाहिए। नीचे प्रस्तुत एक प्रमेय से पता चलता है कि किसी भी सार्वजनिक स्ट्रिंग प्रोटोकॉल को एक व्यक्तिगत स्ट्रिंग प्रोटोकॉल द्वारा अनुकरण किया जा सकता है जो मूल की तुलना में O(log n) अतिरिक्त बिट्स का उपयोग करता है।
-ध्यान दें कि उपरोक्त प्रायिकता असमानताओं में, प्रोटोकॉल के परिणाम को मात्र यादृच्छिक स्ट्रिंग पर निर्भर समझा जाता है; दोनों तार x और y स्थिर रहते हैं। दूसरे शब्दों में, यदि यादृच्छिक स्ट्रिंग r का उपयोग करते समय r (x, y) g (x, y, r) उत्पन्न करता है, फिर g (x, y, r) = f (x, y) स्ट्रिंग r के लिए सभी विकल्पों में से कम से कम 2/3 के लिए।
+ध्यान दें कि उपरोक्त प्रायिकता असमानताओं में, प्रोटोकॉल के परिणाम को मात्र यादृच्छिक स्ट्रिंग पर निर्भर समझा जाता है; दोनों स्ट्रिंग्स x और y स्थिर रहते हैं। दूसरे शब्दों में, यदि यादृच्छिक स्ट्रिंग r का उपयोग करते समय r (x, y) g (x, y, r) उत्पन्न करता है, फिर g (x, y, r) = f (x, y) स्ट्रिंग r के लिए सभी विकल्पों में से कम से कम 2/3 के लिए।
 यादृच्छिक जटिलता को ऐसे प्रोटोकॉल में विनिमय किए गए बिट्स की संख्या के रूप में परिभाषित किया जाता है।
@@ Line 182: / Line 182: @@
 === उदाहरण: जीएच ===
-यादृच्छिक संचार जटिलता के एक और उदाहरण के लिए, हम [[गैप-हैमिंग समस्या|अंतर-हैमिंग समस्या]] (संक्षिप्त जीएच) के रूप में ज्ञात एक उदाहरण की ओर मुड़ते हैं। विधिवत रूप से, ऐलिस और बॉब दोनों बाइनरी संदेश, <math>x,y \in \{-1, +1\}^n</math> बनाए रखते हैं और यह निर्धारित करना चाहते हैं कि तार बहुत समान हैं या यदि वे बहुत समान नहीं हैं।विशेष रूप से, वे निम्नलिखित आंशिक बूलियन फलन की गणना करने के लिए यथासंभव कुछ बिट्स के संचरण की आवश्यकता वाले संचार प्रोटोकॉल को खोजना चाहेंगे,
+यादृच्छिक संचार जटिलता के एक और उदाहरण के लिए, हम [[गैप-हैमिंग समस्या|अंतर-हैमिंग समस्या]] (संक्षिप्त जीएच) के रूप में ज्ञात एक उदाहरण की ओर मुड़ते हैं। विधिवत रूप से, ऐलिस और बॉब दोनों बाइनरी संदेश, <math>x,y \in \{-1, +1\}^n</math> बनाए रखते हैं और यह निर्धारित करना चाहते हैं कि स्ट्रिंग्स बहुत समान हैं या यदि वे बहुत समान नहीं हैं।विशेष रूप से, वे निम्नलिखित आंशिक बूलियन फलन की गणना करने के लिए यथासंभव कुछ बिट्स के संचरण की आवश्यकता वाले संचार प्रोटोकॉल को खोजना चाहेंगे,
 :<math>
@@ Line 193: / Line 193: @@
 :स्पष्ट रूप से, यदि प्रोटोकॉल नियतात्मक होना है, तो उन्हें अपने सभी बिट्स को संवाद करना होगा (यह इसलिए है, क्योंकि यदि कोई नियतात्मक, सख्त सूचकांकों का सबसमुच्चय है जो ऐलिस और बॉब एक दूसरे से रिले करते हैं, तो उस समुच्चय पर स्ट्रिंग्स की एक जोड़ी होने की कल्पना करें में असहमत <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-आयत की न्यूनतम संख्या।
-नियतात्मक संचार जटिलता के लिए कम सीमा प्राप्त करने के साधन के रूप में गैर-नियतात्मक संचार जटिलता उत्पन्न होती है (डाइट्ज़फेलबिंगर एट अल देखें), लेकिन गैर-नकारात्मक मैट्रिसेस के सिद्धांत में भी, जहां यह एक गैर-नकारात्मक आव्यूह के [[गैर-नकारात्मक रैंक (रैखिक बीजगणित)]] पर एक निचली सीमा देता है। ।<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>
-हालांकि सूक्ष्म, इस मॉडल की निचली सीमाएं बेहद मजबूत हैं। अधिक विशेष रूप से, यह स्पष्ट है कि इस वर्ग की समस्याओं पर कोई भी बाध्यता निश्चित रूप से नियतात्मक मॉडल और व्यक्तिगत और सार्वजनिक सिक्का मॉडल में समस्याओं पर समतुल्य सीमाएं लगाती है, लेकिन ऐसी सीमाएं गैर-नियतात्मक संचार मॉडल और क्वांटम संचार मॉडल के लिए भी तुरंत लागू होती हैं।<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|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>

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 09:03, 11 May 2023

Contents