संचार जटिलता

सैद्धांतिक कंप्यूटर विज्ञान में, संचार जटिलता एक समस्या को हल करने के लिए आवश्यक संचार की मात्रा का अध्ययन करती है जब समस्या के इनपुट को दो या दो से अधिक पार्टियों के बीच संगणना वितरित किया जाता है। संचार जटिलता का अध्ययन पहली बार 1979 में एंड्रयू याओ द्वारा पेश किया गया था, जब कई मशीनों के बीच गणना की समस्या का अध्ययन किया गया था।^[1] समस्या को आम तौर पर निम्नानुसार कहा जाता है: दो पक्ष (परंपरागत रूप से ऐलिस और बॉब कहलाते हैं) प्रत्येक को एक (संभावित रूप से भिन्न) प्राप्त होता है $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}$ , आइए एक मैट्रिक्स को परिभाषित करें