Multiparty communication complexity
கோட்பாட்டு கணினி அறிவியலில், பலதரப்பு தகவல்தொடர்பு சிக்கலானது 2 க்கும் மேற்பட்ட வீரர்கள் இருக்கும் அமைப்பில் தகவல்தொடர்பு சிக்கலைப் பற்றிய ஆய்வு ஆகும். இரண்டு வீரர்களால் அறிமுகப்படுத்தப்பட்ட பாரம்பரிய இரு தரப்பு தகவல்தொடர்பு விளையாட்டில், பூலியன் செயல்பாட்டைக் கணக்கிட P1 மற்றும் P2 முயற்சிகள் பிளேயர் P1 க்கு x2 இன் மதிப்பு தெரியும், P2 க்கு x1 இன் மதிப்பு தெரியும், ஆனால் பைக்கு xi இன் மதிப்பு தெரியாது, ஏனெனில் i = 1,2. வேறு வார்த்தைகளில் கூறுவதானால், வீரர்கள் மற்றவரின் மாறிகளை அறிவார்கள், ஆனால் அவர்களின் சொந்தமல்ல. f ஐக் கணக்கிட வீரர்களால் தொடர்பு கொள்ள வேண்டிய குறைந்தபட்ச பிட்களின் எண்ணிக்கை f இன் தகவல்தொடர்பு சிக்கலானது, இது κ (f) ஆல் குறிக்கப்படுகிறது. 1983 ஆம் ஆண்டில் வரையறுக்கப்பட்ட பலதரப்பு தகவல்தொடர்பு விளையாட்டு, 2-கட்சி வழக்கின் சக்திவாய்ந்த பொதுமைப்படுத்தலாகும்ஃ இங்கே வீரர்கள் தங்கள் சொந்தத்தைத் தவிர மற்ற அனைவரின் உள்ளீட்டையும் அறிவார்கள். இந்த பண்பு காரணமாக, சில நேரங்களில் இந்த மாதிரி "நெற்றியில் உள்ள எண்கள்" மாதிரி என்று அழைக்கப்படுகிறது, ஏனெனில் வீரர்கள் ஒரு வட்டமான மேசையைச் சுற்றி அமர்ந்திருந்தால், ஒவ்வொருவரும் தங்கள் சொந்த உள்ளீட்டை நெற்றியில் அணிந்திருந்தால், ஒவ்வொரு வீரரும் மற்ற அனைவரின் உள்ளீட்டையும் பார்ப்பார்கள், தவிர தங்கள் சொந்த. முறையான வரையறை பின்வருமாறுஃ வீரர்கள்ஃ ஒரு பூலியன் செயல்பாட்டைக் கணக்கிட விரும்புகிறார்கள் மாறிகளின் தொகுப்பில் வகுப்புகளின் ஒரு நிலையான பகிர்வு உள்ளது, மேலும் வீரருக்கு ஒவ்வொரு மாறியும் தெரியும், அவற்றில் உள்ளதைத் தவிர. வீரர்கள் வரம்பற்ற கணக்கீட்டு சக்தியைக் கொண்டுள்ளனர், மேலும் அவர்கள் அனைத்து வீரர்களாலும் பார்க்கப்படும் கருப்பு பலகையின் உதவியுடன் தொடர்பு கொள்கிறார்கள். இதன் நோக்கம் கணக்கிடுவது), அதாவது கணக்கீட்டின் முடிவில், ஒவ்வொரு வீரருக்கும் இந்த மதிப்பு தெரியும். கணக்கீட்டின் செலவு என்பது கொடுக்கப்பட்ட உள்ளீடு மற்றும் பகிர்வுக்கு கருப்பு பலகையில் எழுதப்பட்ட பிட்களின் எண்ணிக்கை ஆகும். ஒரு பன்முக நெறிமுறையின் செலவு என்பது தொகுப்பு {0,1} n மற்றும் கொடுக்கப்பட்ட பகிர்விலிருந்து ஏதேனும் ஒன்றுக்கு தொடர்பு கொள்ளப்பட்ட அதிகபட்ச பிட்களின் எண்ணிக்கையாகும். பகிர்வைப் பொறுத்தவரை, ஒரு செயல்பாட்டின்-கட்சி தகவல்தொடர்பு சிக்கலானது, கணக்கிடும் அந்த-கட்சி நெறிமுறைகளின் குறைந்தபட்ச செலவாகும். - கட்சி சமச்சீர் தகவல்தொடர்பு சிக்கலானது தொகுப்பின் அனைத்து k-பகிர்வுகளுக்கும் அதிகபட்சம் எங்கு எடுக்கப்படுகிறது என்று வரையறுக்கப்படுகிறது. மேல் மற்றும் கீழ் வரம்புகள் இரண்டு மற்றும் அதற்கு மேற்பட்ட வீரர்களுக்கான பொதுவான மேல் வரம்பிற்கு, A1, A2, Ak என்ற பிரிவின் மிகச்சிறிய வகுப்புகளில் A1 ஒன்றாகும் என்று வைத்துக்கொள்வோம். பின்னர் P1 ஆல் S இன் எந்த பூலியன் செயல்பாட்டையும் |A1 | + 1 பிட்கள் தகவல்தொடர்புடன் கணக்கிட முடியும்ஃ P2 கருப்பு பலகையில் A1 இன் |A1 | பிட்களை எழுதுகிறது, P1 அதைப் படிக்கிறது, மேலும் கணக்கிடுகிறது மற்றும் மதிப்பை அறிவிக்கிறது. எனவே, பின்வருவனவற்றை எழுதலாம்ஃ பொதுமைப்படுத்தப்பட்ட உள் தயாரிப்பு செயல்பாடு (ஜிஐபி) பின்வருமாறு வரையறுக்கப்படுகிறதுஃ-பிட் திசையன்களாக இருக்கட்டும், நெடுவரிசைகளை திசையன்களாக கொண்டு நேர மேட்ரிக்ஸாக இருக்கட்டும். பின்னர் மாட்ரிக்ஸின் அனைத்து-1 வரிசைகளின் எண்ணிக்கை, மாடுலோ 2 எடுக்கப்பட்டது. வேறு வார்த்தைகளில் கூறுவதானால், திசையன்கள் ஒரு உறுப்பு அடிப்படை தொகுப்பின் துணைக்குழுக்களின் சிறப்பியல்பு திசையன்களுடன் ஒத்திருந்தால், ஜிஐபி இந்த துணைக்குழுக்களின் குறுக்குவெட்டின் சமநிலைக்கு ஒத்திருக்கிறது. இது ஒரு மாறிலி c> 0 உடன் காட்டப்பட்டது. GIP இன் பலதரப்பு தகவல்தொடர்பு சிக்கலின் மேல் வரம்பு ஒரு நிலையான c> 0 உடன் இருப்பதைக் காட்டுகிறது. ஒரு பொதுவான பூலியன் சார்பு f க்கு, அதன் L "1 நெறிமுறையைப் பயன்படுத்துவதன் மூலம் f இன் பலதரப்பு தகவல்தொடர்பு சிக்கலை பின்வருமாறு பிணைக்க முடியும்ஃ பலதரப்பு தகவல்தொடர்பு சிக்கல் மற்றும் சூடோரேண்டம் ஜெனரேட்டர்கள் ஒரு சூடோரேண்டம் எண் ஜெனரேட்டரின் கட்டுமானம் GIP செயல்பாட்டிற்கான BNS கீழ் வரம்பை அடிப்படையாகக் கொண்டது. பயன்பாட்டு கணித தகவல் கோட்பாடு