סיבוכיות תקשורת – הבדלי גרסאות

המונח '''סיבוכיות תקשורת''' היא מונח ב[[מדעי המחשב]]: [[סיבוכיות]] שבה המדד הוא כמות המידע המועברת בתקשורת בין שני צדדים. המונח הוצג ע"יעל ידי יאו בשנת 1979{{הערה|Yao, A. C. (1979), "Some Complexity Questions Related to Distributed Computing", Proc. of 11th STOC, 14: 209–213}}.

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