Multiparty communication complexity
نظریاتی کمپیوٹر سائنس میں، کثیر الجہتی مواصلاتی پیچیدگی اس ترتیب میں مواصلاتی پیچیدگی کا مطالعہ ہے جہاں 2 سے زیادہ کھلاڑی ہوتے ہیں۔ روایتی دو طرفہ مواصلاتی کھیل میں، جسے دو کھلاڑیوں نے متعارف کرایا ہے، پی 1 اور پی 2 بولین فنکشن کا حساب لگانے کی کوشش کرتے ہیں پلیئر پی 1 کو ایکس 2 کی قیمت معلوم ہوتی ہے، پی 2 کو ایکس 1 کی قیمت معلوم ہوتی ہے، لیکن پائی کو xi کی قیمت معلوم نہیں ہے، کیونکہ i = 1، 2 ہے۔ دوسرے لفظوں میں، کھلاڑی دوسرے کے متغیرات کو جانتے ہیں، لیکن ان کے اپنے نہیں۔ بٹس کی کم از کم تعداد جو کھلاڑیوں کو f کا حساب لگانے کے لیے بتانی چاہیے وہ f کی مواصلاتی پیچیدگی ہے، جسے κ (f) سے ظاہر کیا جاتا ہے۔ ملٹی پارٹی کمیونیکیشن گیم، جس کی تعریف 1983 میں کی گئی تھی، 2 پارٹی کیس کی ایک طاقتور عمومی شکل ہے: یہاں کھلاڑی اپنے علاوہ دیگر تمام ان پٹ کو جانتے ہیں۔ اس خاصیت کی وجہ سے، بعض اوقات اس ماڈل کو "ماتھے پر نمبر" ماڈل کہا جاتا ہے، کیونکہ اگر کھلاڑی گول میز کے ارد گرد بیٹھے ہوتے، ہر ایک نے ماتھے پر اپنا ان پٹ پہنا ہوتا، تو ہر کھلاڑی کو دوسروں کا ان پٹ نظر آتا، سوائے ان کے اپنے کے۔ رسمی تعریف مندرجہ ذیل ہے: کھلاڑی: بولین فنکشن کا حساب لگانے کا ارادہ رکھتے ہیں متغیرات کے سیٹ پر کلاسوں کی ایک مقررہ تقسیم ہوتی ہے، اور کھلاڑی ہر متغیر کو جانتا ہے، سوائے ان کے، کے۔ کھلاڑیوں کے پاس لامحدود کمپیوٹیشنل طاقت ہوتی ہے، اور وہ بلیک بورڈ کی مدد سے بات چیت کرتے ہیں، جسے تمام کھلاڑی دیکھتے ہیں۔ مقصد حساب لگانا ہے)، اس طرح کہ حساب کے اختتام پر، ہر کھلاڑی اس قدر کو جانتا ہے۔ حساب کی لاگت دی گئی ان پٹ اور پارٹیشن کے لیے بلیک بورڈ پر لکھے گئے بٹس کی تعداد ہے۔ ملٹی پارٹی پروٹوکول کی لاگت سیٹ {0,1} n اور دی گئی پارٹیشن میں سے کسی کے لیے بھیجے گئے بٹس کی زیادہ سے زیادہ تعداد ہے۔ پارٹیشن کے حوالے سے، کسی فنکشن کی-پارٹی مواصلاتی پیچیدگی، ان-پارٹی پروٹوکول کی کم از کم لاگت ہے جو حساب کرتی ہے۔ کی-پارٹی سمیٹرک مواصلاتی پیچیدگی کی تعریف اس طرح کی جاتی ہے جہاں سیٹ کے تمام k-پارٹیشنز پر زیادہ سے زیادہ لیا جاتا ہے۔ اوپری اور نچلی حدود دو اور زیادہ کھلاڑیوں کے لیے عام اوپری باؤنڈ کے لیے، فرض کریں کہ A1 پارٹیشن A1، A2،.، Ak کی سب سے چھوٹی کلاسوں میں سے ایک ہے۔ پھر P1 مواصلات کے |A1 | + 1 بٹس کے ساتھ S کے کسی بھی بولین فنکشن کا حساب لگا سکتا ہے: P2 بلیک بورڈ پر A1 کے |A1 | بٹس کو لکھتا ہے، P1 اسے پڑھتا ہے، اور قدر کا حساب لگاتا ہے اور اعلان کرتا ہے۔ لہذا، مندرجہ ذیل لکھا جا سکتا ہے: جنرلائزڈ انر پروڈکٹ فنکشن (جی آئی پی) کی تعریف اس طرح کی گئی ہے: آئیے-بٹ ویکٹر، اور آئیے ٹائم میٹرکس، کالموں کے ساتھ ویکٹر کے طور پر۔ پھر میٹرکس کی تمام 1 قطاروں کا نمبر ہے، جو ماڈیولو 2 لیا گیا ہے۔ دوسرے لفظوں میں، اگر ویکٹر کسی عنصر کے بیس سیٹ کے ذیلی سیٹوں کے خصوصیت والے ویکٹر سے مطابقت رکھتے ہیں، تو جی آئی پی ان ذیلی سیٹوں کے چوراہے کی برابری سے مطابقت رکھتا ہے۔ یہ دکھایا گیا تھا کہ ایک مستقل c> 0 کے ساتھ۔ جی آئی پی کی کثیر فریقی مواصلاتی پیچیدگی پر ایک اوپری حد سے پتہ چلتا ہے کہ مستقل c> 0 کے ساتھ۔ عام بولین فنکشن f کے لیے، کوئی بھی اس کے L "1 معیار کا استعمال کرتے ہوئے f کی ملٹی پارٹی مواصلاتی پیچیدگی کو پابند کر سکتا ہے: ملٹی پارٹی مواصلاتی پیچیدگی اور سیوڈورانڈم جنریٹر ایک سیوڈورانڈم نمبر جنریٹر کی تعمیر جی آئی پی فنکشن کے لیے بی این ایس لوور باؤنڈ پر مبنی تھی۔ اطلاقی ریاضی انفارمیشن تھیوری