Multiparty communication complexity
তাত্ত্বিক কম্পিউটার বিজ্ঞানে, বহুদলীয় যোগাযোগ জটিলতা হল এমন পরিবেশে যোগাযোগ জটিলতার অধ্যয়ন যেখানে 2 জনের বেশি খেলোয়াড় রয়েছে। দুই খেলোয়াড়ের দ্বারা প্রবর্তিত ঐতিহ্যবাহী দ্বিদলীয় যোগাযোগ খেলায়, পি1 এবং পি2 একটি বুলিয়ান ফাংশন গণনা করার চেষ্টা করে প্লেয়ার পি1 x2-এর মান জানে, পি2 x1-এর মান জানে, কিন্তু পাই xi-এর মান জানে না, i = 1,2-এর জন্য। অন্য কথায়, খেলোয়াড়রা অন্যের পরিবর্তনশীল বিষয়গুলি জানে, তবে তাদের নিজস্ব নয়। এফ গণনা করার জন্য খেলোয়াড়দের ন্যূনতম যে সংখ্যক বিট যোগাযোগ করতে হবে তা হল এফ-এর যোগাযোগ জটিলতা, যা κ (এফ) দ্বারা চিহ্নিত করা হয়। 1983 সালে সংজ্ঞায়িত মাল্টিপার্টি কমিউনিকেশন গেমটি 2-পক্ষের মামলার একটি শক্তিশালী সাধারণীকরণঃ এখানে খেলোয়াড়রা তাদের নিজস্ব ব্যতীত অন্য সকলের ইনপুট জানেন। এই বৈশিষ্ট্যের কারণে, কখনও কখনও এই মডেলটিকে "কপালে সংখ্যা" মডেল বলা হয়, কারণ খেলোয়াড়রা যদি একটি গোল টেবিলের চারপাশে বসে থাকে, প্রত্যেকে কপালে তাদের নিজস্ব ইনপুট পরে থাকে, তবে প্রতিটি খেলোয়াড় তাদের নিজস্ব ছাড়া অন্য সকলের ইনপুট দেখতে পাবে। আনুষ্ঠানিক সংজ্ঞাটি নিম্নরূপঃ খেলোয়াড়ঃ একটি বুলিয়ান ফাংশন গণনা করার অভিপ্রায় ভেরিয়েবলের সেটে ক্লাসের একটি নির্দিষ্ট পার্টিশন থাকে এবং খেলোয়াড় প্রতিটি ভেরিয়েবল জানেন, এর জন্য ব্যতীত। খেলোয়াড়দের সীমাহীন গণনামূলক ক্ষমতা রয়েছে এবং তারা একটি ব্ল্যাকবোর্ডের সাহায্যে যোগাযোগ করে, যা সমস্ত খেলোয়াড় দেখে। লক্ষ্য হল গণনা করা), যাতে গণনার শেষে, প্রতিটি খেলোয়াড় এই মানটি জানে। গণনার খরচ হল প্রদত্ত ইনপুট এবং পার্টিশনের জন্য ব্ল্যাকবোর্ডে লেখা বিটের সংখ্যা। একটি মাল্টিপার্টি প্রোটোকলের মূল্য হল সেট {0,1} এন এবং প্রদত্ত পার্টিশন থেকে যে কোনও বিটের জন্য যোগাযোগ করা সর্বাধিক সংখ্যা। পার্টিশনের ক্ষেত্রে কোনও ফাংশনের-পার্টি যোগাযোগ জটিলতা হল সেই-পার্টি প্রোটোকলগুলির ন্যূনতম খরচ যা গণনা করে। এর-দলীয় প্রতিসম যোগাযোগ জটিলতাকে সংজ্ঞায়িত করা হয় যেখানে সেটের সমস্ত কে-পার্টিশনের উপর সর্বাধিক নেওয়া হয়। উচ্চ এবং নিম্ন সীমা দুই বা ততোধিক খেলোয়াড়ের জন্য একটি সাধারণ উচ্চ সীমার জন্য, ধরা যাক যে এ1 হল এ1, এ2, এ. কে. বিভাগের ক্ষুদ্রতম শ্রেণীগুলির মধ্যে একটি। তারপর পি1 |A1। + 1 বিট যোগাযোগের মাধ্যমে এস-এর যে কোনও বুলিয়ান ফাংশন গণনা করতে পারেঃ পি2 ব্ল্যাকবোর্ডে এ1-এর |A1। বিটগুলি লিখে রাখে, পি1 এটি পড়ে এবং গণনা করে এবং মান ঘোষণা করে। সুতরাং, নিম্নলিখিতগুলি লেখা যেতে পারেঃ জেনারেলাইজড ইনার প্রোডাক্ট ফাংশন (জিআইপি) নিম্নরূপ সংজ্ঞায়িত করা হয়েছেঃ ধরা যাক-বিট ভেক্টর, এবং টাইম ম্যাট্রিক্স, ভেক্টর হিসাবে কলাম সহ। তারপর ম্যাট্রিক্সের সমস্ত-1 সারির সংখ্যা, মডুলো 2 নেওয়া হয়েছে। অন্য কথায়, যদি ভেক্টরগুলি কোনও উপাদান বেস-সেটের উপসেটগুলির চরিত্রগত ভেক্টরগুলির সাথে মিলে যায়, তবে জিআইপি এই উপসেটগুলির ছেদনের সমতার সাথে মিলে যায়। এটি দেখানো হয়েছিল যে একটি ধ্রুবক c> 0 সহ। জিআইপি-র বহুদলীয় যোগাযোগ জটিলতার একটি উপরের সীমা দেখায় যে একটি ধ্রুবক সি> 0 সহ। একটি সাধারণ বুলিয়ান ফাংশন f-এর জন্য, নিম্নলিখিতভাবে তার L "1 আদর্শ ব্যবহার করে f-এর বহুদলীয় যোগাযোগ জটিলতাকে আবদ্ধ করা যেতে পারেঃ বহুদলীয় যোগাযোগ জটিলতা এবং ছদ্মবেশী জেনারেটর একটি ছদ্মবেশী সংখ্যা জেনারেটরের নির্মাণ জিআইপি ফাংশনের জন্য নিম্ন সীমার উপর ভিত্তি করে তৈরি করা হয়েছিল। ফলিত গণিত তথ্য তত্ত্ব