Multiparty communication complexity
ಸೈದ್ಧಾಂತಿಕ ಗಣಕಯಂತ್ರ ವಿಜ್ಞಾನದಲ್ಲಿ, ಬಹುಪಕ್ಷೀಯ ಸಂವಹನ ಸಂಕೀರ್ಣತೆಯು ಎರಡಕ್ಕಿಂತ ಹೆಚ್ಚು ಆಟಗಾರರು ಇರುವ ವ್ಯವಸ್ಥೆಯಲ್ಲಿ ಸಂವಹನ ಸಂಕೀರ್ಣತೆಯ ಅಧ್ಯಯನವಾಗಿದೆ. ಪರಿಚಯಿಸಲಾದ ಸಾಂಪ್ರದಾಯಿಕ ಎರಡು-ಪಕ್ಷಗಳ ಸಂವಹನ ಆಟದಲ್ಲಿ, ಇಬ್ಬರು ಆಟಗಾರರು, ಪಿ1 ಮತ್ತು ಪಿ2 ಬೂಲಿಯನ್ ಕಾರ್ಯವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ಪ್ರಯತ್ನಿಸುತ್ತಾರೆ, ಆಟಗಾರ ಪಿ1ಗೆ x2 ಮೌಲ್ಯ ತಿಳಿದಿದೆ, ಪಿ2ಗೆ x1 ಮೌಲ್ಯ ತಿಳಿದಿದೆ, ಆದರೆ ಪೈಗೆ xi ಮೌಲ್ಯ ತಿಳಿದಿಲ್ಲ, ಏಕೆಂದರೆ i = 1,2. ಬೇರೆ ರೀತಿಯಲ್ಲಿ ಹೇಳುವುದಾದರೆ, ಆಟಗಾರರು ಇತರರ ಅಸ್ಥಿರಗಳನ್ನು ತಿಳಿದಿದ್ದಾರೆ, ಆದರೆ ತಮ್ಮದೇ ಆದದ್ದಲ್ಲ. ಎಫ್ ಅನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ಆಟಗಾರರು ಸಂವಹನ ಮಾಡಬೇಕಾದ ಕನಿಷ್ಠ ಸಂಖ್ಯೆಯ ಬಿಟ್ಗಳು ಎಫ್ ನ ಸಂವಹನ ಸಂಕೀರ್ಣತೆಯಾಗಿದೆ, ಇದನ್ನು κ (ಎಫ್) ನಿಂದ ಸೂಚಿಸಲಾಗುತ್ತದೆ. 1983ರಲ್ಲಿ ವ್ಯಾಖ್ಯಾನಿಸಲಾದ ಬಹುಪಕ್ಷೀಯ ಸಂವಹನ ಆಟವು 2-ಪಕ್ಷಗಳ ಪ್ರಕರಣದ ಪ್ರಬಲವಾದ ಸಾಮಾನ್ಯೀಕರಣವಾಗಿದೆಃ ಇಲ್ಲಿ ಆಟಗಾರರು ತಮ್ಮದೇ ಆದದ್ದನ್ನು ಹೊರತುಪಡಿಸಿ ಇತರರ ಎಲ್ಲಾ ಇನ್ಪುಟ್ಗಳನ್ನು ತಿಳಿದಿದ್ದಾರೆ. ಈ ಗುಣಲಕ್ಷಣದ ಕಾರಣದಿಂದಾಗಿ, ಕೆಲವೊಮ್ಮೆ ಈ ಮಾದರಿಯನ್ನು "ಹಣೆಯ ಮೇಲಿನ ಸಂಖ್ಯೆಗಳು" ಮಾದರಿ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ, ಏಕೆಂದರೆ ಆಟಗಾರರು ದುಂಡಗಿನ ಮೇಜಿನ ಸುತ್ತಲೂ ಕುಳಿತಿದ್ದರೆ, ಪ್ರತಿಯೊಬ್ಬರೂ ಹಣೆಯ ಮೇಲೆ ತಮ್ಮದೇ ಆದ ಇನ್ಪುಟ್ ಅನ್ನು ಧರಿಸಿದ್ದರೆ, ಪ್ರತಿಯೊಬ್ಬ ಆಟಗಾರನು ತಮ್ಮ ಸ್ವಂತವನ್ನು ಹೊರತುಪಡಿಸಿ ಇತರರ ಎಲ್ಲಾ ಇನ್ಪುಟ್ಗಳನ್ನು ನೋಡುತ್ತಾನೆ. ಔಪಚಾರಿಕ ವ್ಯಾಖ್ಯಾನವು ಈ ಕೆಳಗಿನಂತಿದೆಃ ಆಟಗಾರರುಃ ಬೂಲಿಯನ್ ಕಾರ್ಯವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ಉದ್ದೇಶಿಸುತ್ತಾರೆ ಅಸ್ಥಿರಗಳ ಗುಂಪಿನಲ್ಲಿ ವರ್ಗಗಳ ಒಂದು ಸ್ಥಿರವಾದ ವಿಭಾಗವಿದೆ, ಮತ್ತು ಆಟಗಾರನು ಪ್ರತಿಯೊಂದು ಅಸ್ಥಿರವನ್ನು ತಿಳಿದಿರುತ್ತಾನೆ, ಅದರಲ್ಲಿರುವುದನ್ನು ಹೊರತುಪಡಿಸಿ. ಆಟಗಾರರು ಅನಿಯಮಿತ ಗಣನೆಯ ಶಕ್ತಿಯನ್ನು ಹೊಂದಿರುತ್ತಾರೆ ಮತ್ತು ಅವರು ಎಲ್ಲಾ ಆಟಗಾರರು ನೋಡುವ ಕಪ್ಪು ಹಲಗೆಯ ಸಹಾಯದಿಂದ ಸಂವಹನ ನಡೆಸುತ್ತಾರೆ. ಗಣನೆಯ ಕೊನೆಯಲ್ಲಿ, ಪ್ರತಿಯೊಬ್ಬ ಆಟಗಾರನಿಗೂ ಈ ಮೌಲ್ಯವು ತಿಳಿದಿರುತ್ತದೆ). ಗಣನೆಯ ವೆಚ್ಚವು ನೀಡಲಾದ ಇನ್ಪುಟ್ ಮತ್ತು ವಿಭಾಗಕ್ಕಾಗಿ ಕಪ್ಪು ಹಲಗೆಯಲ್ಲಿ ಬರೆಯಲಾದ ಬಿಟ್ಗಳ ಸಂಖ್ಯೆಯಾಗಿದೆ. ಬಹುಪಕ್ಷೀಯ ಶಿಷ್ಟಾಚಾರದ ವೆಚ್ಚವು ಸೆಟ್ {0,1} n ಮತ್ತು ನೀಡಲಾದ ವಿಭಾಗದಿಂದ ಯಾವುದೇ ಸಂವಹನ ಮಾಡಲಾದ ಬಿಟ್ಗಳ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯಾಗಿದೆ. ವಿಭಜನೆಗೆ ಸಂಬಂಧಿಸಿದಂತೆ ಒಂದು ಕಾರ್ಯದ-ಪಕ್ಷದ ಸಂವಹನ ಸಂಕೀರ್ಣತೆಯು, ಲೆಕ್ಕಾಚಾರ ಮಾಡುವ ಆ-ಪಕ್ಷದ ಶಿಷ್ಟಾಚಾರಗಳ ಕನಿಷ್ಠ ವೆಚ್ಚವಾಗಿದೆ. - ಪಕ್ಷದ ಸಮ್ಮಿತೀಯ ಸಂವಹನ ಸಂಕೀರ್ಣತೆಯನ್ನು ಸೆಟ್ನ ಎಲ್ಲಾ ಕೆ-ವಿಭಾಗಗಳ ಮೇಲೆ ಗರಿಷ್ಠವನ್ನು ತೆಗೆದುಕೊಳ್ಳಲಾಗುತ್ತದೆ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. ಎರಡು ಮತ್ತು ಹೆಚ್ಚಿನ ಆಟಗಾರರಿಗೆ ಸಾಮಾನ್ಯ ಮೇಲಿನ ಮಿತಿಗಾಗಿ, A1, A2,., Ak ವಿಭಾಗದ ಚಿಕ್ಕ ವರ್ಗಗಳಲ್ಲಿ A1 ಒಂದಾಗಿದೆ ಎಂದು ಭಾವಿಸೋಣ. ನಂತರ P1 ಯು S ನ ಯಾವುದೇ ಬೂಲಿಯನ್ ಕಾರ್ಯವನ್ನು |A1 | + 1 ಬಿಟ್ ಸಂವಹನದೊಂದಿಗೆ ಲೆಕ್ಕಾಚಾರ ಮಾಡಬಹುದುಃ P2 ಕಪ್ಪು ಹಲಗೆಯ ಮೇಲೆ A1 ನ |A1 | ಬಿಟ್ಗಳನ್ನು ಬರೆಯುತ್ತದೆ, P1 ಅದನ್ನು ಓದುತ್ತದೆ ಮತ್ತು ಮೌಲ್ಯವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡುತ್ತದೆ ಮತ್ತು ಘೋಷಿಸುತ್ತದೆ. ಆದ್ದರಿಂದ, ಈ ಕೆಳಗಿನವುಗಳನ್ನು ಬರೆಯಬಹುದುಃ ಜನರಲೈಸ್ಡ್ ಇನ್ನರ್ ಪ್ರಾಡಕ್ಟ್ ಫಂಕ್ಷನ್ (ಜಿಐಪಿ) ಅನ್ನು ಈ ಕೆಳಗಿನಂತೆ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆಃ-ಬಿಟ್ ವಾಹಕಗಳಾಗಿರಲಿ, ಮತ್ತು ಕಾಲಮ್ಗಳನ್ನು ವಾಹಕಗಳನ್ನಾಗಿ ಹೊಂದಿರುವ ಟೈಮ್ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಆಗಿರಲಿ. ನಂತರ ಮಾಡ್ಯುಲೋ 2 ಎಂದು ತೆಗೆದುಕೊಳ್ಳಲಾದ ಮ್ಯಾಟ್ರಿಕ್ಸ್ನ ಎಲ್ಲಾ-1 ಸಾಲುಗಳ ಸಂಖ್ಯೆ. ಬೇರೆ ರೀತಿಯಲ್ಲಿ ಹೇಳುವುದಾದರೆ, ವಾಹಕಗಳು ಒಂದು ಅಂಶದ ಬೇಸ್-ಸೆಟ್ನ ಉಪಗುಂಪುಗಳ ವಿಶಿಷ್ಟ ವಾಹಕಗಳಿಗೆ ಅನುಗುಣವಾಗಿದ್ದರೆ, ಜಿಐಪಿ ಈ ಉಪಗುಂಪುಗಳ ಛೇದನದ ಸಮಾನತೆಗೆ ಅನುಗುಣವಾಗಿರುತ್ತದೆ. ಸ್ಥಿರಾಂಕ c> 0 ಎಂದು ತೋರಿಸಲಾಗಿದೆ. ಜಿಐಪಿಯ ಬಹುಪಕ್ಷೀಯ ಸಂವಹನ ಸಂಕೀರ್ಣತೆಯ ಮೇಲಿನ ಮಿತಿಯು ಸ್ಥಿರಾಂಕ ಸಿ> 0 ಎಂದು ತೋರಿಸುತ್ತದೆ. ಸಾಮಾನ್ಯ ಬೂಲಿಯನ್ ಫಂಕ್ಷನ್ f ಗೆ, ಅದರ L "1 ಮಾನದಂಡವನ್ನು ಬಳಸಿಕೊಂಡು f ನ ಬಹುಪಕ್ಷೀಯ ಸಂವಹನ ಸಂಕೀರ್ಣತೆಯನ್ನು ಈ ಕೆಳಗಿನಂತೆ ಬಂಧಿಸಬಹುದುಃ ಮಲ್ಟಿಪಾರ್ಟಿ ಸಂವಹನ ಸಂಕೀರ್ಣತೆ ಮತ್ತು ಸೂಡೊರಾಂಡಮ್ ಜನರೇಟರ್ಗಳು ಸೂಡೊರಾಂಡಮ್ ಸಂಖ್ಯೆ ಜನರೇಟರ್ನ ನಿರ್ಮಾಣವು ಜಿಐಪಿ ಕಾರ್ಯಕ್ಕಾಗಿ ಬಿಎನ್ಎಸ್ ಲೋವರ್ ಬೌಂಡ್ ಅನ್ನು ಆಧರಿಸಿದೆ. ಅನ್ವಯಿಕ ಗಣಿತ ಮಾಹಿತಿ ಸಿದ್ಧಾಂತ