संचार जटिलता

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