Multiparty communication complexity
सैद्धांतिक कंप्यूटर विज्ञान में, बहुपक्षीय संचार जटिलता उस सेटिंग में संचार जटिलता का अध्ययन है जहां 2 से अधिक खिलाड़ी हैं। दो खिलाड़ियों द्वारा शुरू किए गए पारंपरिक दो-पक्षीय संचार खेल में, पी1 और पी2 एक बूलियन कार्य की गणना करने का प्रयास करते हैं, खिलाड़ी पी1 को एक्स2 का मूल्य पता होता है, पी2 को एक्स1 का मूल्य पता होता है, लेकिन पाई को xi का मूल्य नहीं पता होता है, क्योंकि आई = 1,2। दूसरे शब्दों में, खिलाड़ी दूसरे के चर को जानते हैं, लेकिन अपने चर को नहीं। एफ की गणना करने के लिए खिलाड़ियों द्वारा संचारित किए जाने वाले बिट्स की न्यूनतम संख्या एफ की संचार जटिलता है, जिसे κ (एफ) द्वारा दर्शाया जाता है। 1983 में परिभाषित बहुपक्षीय संचार खेल, 2-पक्षीय मामले का एक शक्तिशाली सामान्यीकरण हैः यहाँ खिलाड़ी अपने स्वयं के को छोड़कर अन्य सभी के इनपुट को जानते हैं। इस गुण के कारण, कभी-कभी इस मॉडल को "माथे पर संख्या" मॉडल कहा जाता है, क्योंकि यदि खिलाड़ी एक गोल मेज के चारों ओर बैठे थे, प्रत्येक ने माथे पर अपना इनपुट पहना हुआ था, तो प्रत्येक खिलाड़ी अपने स्वयं के को छोड़कर अन्य सभी के इनपुट को देखेगा। औपचारिक परिभाषा इस प्रकार हैः खिलाड़ीः एक बूलियन फलन की गणना करने का इरादा चरों के समूह पर वर्गों का एक निश्चित विभाजन होता है, और खिलाड़ी प्रत्येक चर को जानता है, सिवाय उन चरों के जिनके लिए। खिलाड़ियों के पास असीमित कम्प्यूटेशनल शक्ति होती है, और वे एक ब्लैकबोर्ड की मदद से संवाद करते हैं, जिसे सभी खिलाड़ी देखते हैं। इसका उद्देश्य गणना करना है), जैसे कि गणना के अंत में, प्रत्येक खिलाड़ी इस मूल्य को जानता है। गणना की लागत दिए गए इनपुट और विभाजन के लिए ब्लैकबोर्ड पर लिखे गए बिट्स की संख्या है। एक बहुपक्षीय प्रोटोकॉल की लागत सेट {0,1} n और दिए गए विभाजन से किसी के लिए संचारित बिट्स की अधिकतम संख्या है। विभाजन के संबंध में किसी कार्य की-पक्षीय संचार जटिलता, उन-पक्षीय प्रोटोकॉल की न्यूनतम लागत है जो गणना करते हैं। की-पार्टी सममित संचार जटिलता को परिभाषित किया गया है जहां सेट के सभी के-विभाजनों पर अधिकतम लिया जाता है। ऊपरी और निचली सीमाएँ दो और अधिक खिलाड़ियों के लिए एक सामान्य ऊपरी सीमा के लिए, मान लीजिए कि ए1 विभाजन ए1, ए2, ए. के. के सबसे छोटे वर्गों में से एक है। फिर P1 संचार के |A1। + 1 बिट्स के साथ S के किसी भी बूलियन फ़ंक्शन की गणना कर सकता हैः P2 ब्लैकबोर्ड पर A1 के |A1। बिट्स को लिख देता है, P1 इसे पढ़ता है, और गणना करता है और मूल्य की घोषणा करता है। तो, निम्नलिखित को लिखा जा सकता हैः सामान्यीकृत आंतरिक उत्पाद फलन (जी. आई. पी.) को निम्नानुसार परिभाषित किया गया हैः मान लीजिए-बिट वैक्टर, और मान लीजिए कि वेक्टर के रूप में कॉलम के साथ समय मैट्रिक्स। फिर मैट्रिक्स की सभी-1 पंक्तियों की संख्या है, जिसे मॉड्यूलो 2 लिया गया है। दूसरे शब्दों में, यदि वैक्टर किसी तत्व आधार-समुच्चय के उपसमुच्चय के विशिष्ट वैक्टरों के अनुरूप हैं, तो जी. आई. पी. इन उपसमुच्चय के प्रतिच्छेदन की समानता के अनुरूप है। यह दिखाया गया था कि एक स्थिरांक c> 0 के साथ। जी. आई. पी. की बहुपक्षीय संचार जटिलता पर एक ऊपरी सीमा से पता चलता है कि एक स्थिरांक सी> 0 के साथ। एक सामान्य बूलियन फलन f के लिए, कोई भी अपने L "1 मानक का उपयोग करके f की बहुपक्षीय संचार जटिलता को इस प्रकार बांध सकता हैः बहुपक्षीय संचार जटिलता और छद्म-रैंडम जनरेटर एक छद्म-रैंडम संख्या जनरेटर का निर्माण GIP फलन के लिए BNS निचली सीमा पर आधारित था। अनुप्रयुक्त गणित सूचना सिद्धांत