סיבוכיות תקשורת

המונח סיבוכיות תקשורת היא מונח במדעי המחשב: סיבוכיות שבה המדד הוא כמות המידע המועברת בתקשורת בין שני צדדים. המונח הוצג על ידי יאו בשנת 1979.

סיבוכיות התקשורת בוחנת את המצב הבא: ישנם שני משתתפים אליס ובוב, אליס מקבלת מחרוזת של n-ביטים x ובוב מקבל מחרוזת ביטים אחרת y באותו האורך. מטרתם היא שאחד מהמשתתפים (נניח בוב) יחשב פונקציה מסוימת (f(x,y תוך כדי קיום תקשורת מינמלית בין המשתתפים. יש לציין שבהגדרה זו אין התחשבות במספר הצעדים החישוביים או בזיכרון הדרוש לכל אחד מהמשתתפים. סיבוכיות תקשורת נועדה לכמת את כמות המידע שנדרש להעביר על מנת לבצע חישוב מבוזר שכזה.

כמובן, אליס ובוב יכולים לחשב את (f(x,y ע״י כך שאליס תשלח את כל n הביטים שהיא קיבלה לבוב, שלאחר קבלתם יוכל לחשב באופן מקומי את הפונקציה (f(x,y ללא עזרה נוספת מאליס. המטרה בחקר סיבוכיות תקשורת היא למצוא שיטות מתקדמות לחישוב f שדורשות העברה של פחות מ-n ביטים, או להוכיח שכמות מסוימת של ביטים הכרחית לחישוב f.

הבעיה, והכללותיה למצבים בהם יותר משני משתתפים באה לידי ביטוי בהקשרים רבים: בעיצוב מעגלי VLSI למשל, רוצים למזער את האנרגיה שהמעגל צורך על ידי הפחתת מספר האותות המועברים בין רכיבים שונים. תחומים נוספים בהם באה הבעיה לידי ביטוי הם למשל מבני נתונים ואופטימיזציה של רשתות תקשורת.

חסמים תחתונים על סיבוכיות התקשורת משמשים, בין היתר, להוכחת חסמים תחתונים למבני נתונים, אלגוריתמי זרימה, מעגלי VLSI ועוד.

לקריאה נוספת

• Kushilevitz, E. and N. Nisan. Communication complexity. Cambridge University Press, 1997.
• Brassard, G. Quantum communication complexity: a survey. http://arxiv.org/abs/quant-ph/0101005
• Dietzfelbinger, M., J. Hromkovic, J., and G. Schnitger, "A comparison of two lower-bound methods for communication complexity", Theoret. Comput. Sci. 168, 1996. 39-51.
• Raz, Ran. "Circuit and Communication Complexity." In Computational Complexity Theory. Steven Rudich and Avi Wigderson, eds. American Mathematical Society Institute for Advanced Study, 2004. 129-137.
• A. C. Yao, "Some Complexity Questions Related to Distributed Computing", Proc. of 11th STOC, pp. 209–213, 1979. 14
• I. Newman, Private vs. Common Random Bits in Communication Complexity, Information Processing Letters 39, 1991, pp. 67–71.

הערות שוליים

ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום למכלול ולהרחיב אותו.