מה זו סיבוכיות תקשורת?

בתורת הסיבוכיות מדברים על השאלה “איזו כמות של משאבים נדרשת בשביל לבצע חישוב מסויים?”. לרוב המשאבים הם זמן או זכרון מחשב; אני רוצה לדבר הפעם על מדד סיבוכיות שונה למדי באופיו, שהוא הבסיס לתחום יפה ומעניין בתורת הסיבוכיות - סיבוכיות תקשורת.

הרעיון הבסיסי הוא זה: יש לנו שני “שחקנים”, אליס ובוב. אליס מחזיקה בקלט כלשהו \( x \) ובוב מחזיק בקלט כלשהו \( y \). אליס ובוב רוצים לחשב פונקציה כלשהי בשני משתנים, \( f\left(x,y\right) \). לצורך כך, ברור שחייב לעבור מידע כלשהו מאליס אל בוב ולהפך - אלא אם \( f \) טריוויאלית למדי, לא ייתכן שאליס תוכל לחשב את \( f \) בלי לדעת משהו על \( y \), ואותו הדבר עבור בוב ו-\( x \). לכן, בהינתן \( f \), עולה השאלה - כמה מידע אליס ובוב צריכים להחליף ביניהם כדי שיוכלו לחשב את \( f \)?

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

הדוגמה היא חישוב חציון. חציון של קבוצת מספרים (“קבוצה”, לא במובן התורת-קבוצותניקי הרגיל - אותו איבר יכול להופיע בקבוצה כמה פעמים. פורמלית המתמטיקאים קוראים לזה Multiset) הוא מספר שקטן בדיוק ממחציתם של המספרים, וגדול בדיוק ממחציתם של המספרים. לא תמיד זה אפשרי - למשל, בקבוצה \( \left\{ 1,2,3,4\right\} \) אין חציון אלא שני “כמעט חציונים”, \( 2 \) ו-\( 3 \). במקרה הזה נאמר שרירותית ש-\( 2 \) הוא החציון. בקבוצה \( \left\{ 3,6,2,2,4\right\} \) קל לראות ש-3 הוא החציון, וכדומה.

כעת הן לאליס והן לבוב יהיו קבוצות של מספרים מ-1 עד \( n \). קבוצה כזו אפשר לייצג בעזרת \( n \) ביטים: הביט ה-\( i \) הוא 1 אם המספר \( i \) שייך לקבוצה ו-0 אחרת. למשל, הקבוצה \( \left\{ 2,4,5\right\} \) מיוצגת על ידי המחרוזת \( 01011 \). \( f\left(x,y\right) \) יהיה פשוט מספרו של החציון של הקבוצות \( x\cup y \) (שוב, אם יש איבר זהה ב-\( x \) וב-\( y \), באיחוד הוא יופיע פעמיים). כדי לייצג את המספר הזה צריך \( \lg n \) ביטים - למעשה, כדי שאליס תשלח לבוב מספר כלשהו צריך \( \lg n \) ביטים. מה שמפתיע כאן הוא שכדי לחשב את החציון המשותף לא צריך הרבה יותר מאשר \( \lg n \) ביטים - סיבוכיות התקשורת של \( f \) היא \( O\left(\lg n\right) \).

כמו שקורה לעתים קרובות בסיבוכיות, התוצאה הזו היא מסוג הדברים שכשאני שומע עליהם לראשונה אני חושב “אין סיכוי. לא נכון. שקר וכזב. בלתי אפשרי. אין שום דרך לעשות את זה”. היופי בסיבוכיות הוא איך שמוצאים דרך לעשות את זה. הפתרון כאן הוא אמנם מחוכם ויפה למדי אבל לא מסובך במיוחד, ואני מקווה לא לאבד קוראים במהלכו. אגב, אני ממליץ לכולכם לנסות ולחשוב על הבעיה לפני שתקראו את הפתרון; כפי שקורה לעתים קרובות בעניינים הללו, עד שלא יושבים וחושבים אישית על הבעיה קשה להבין עד כמה היא קשה/טריקית ומדוע הפתרון שלה הוא יפה.

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

עכשיו נציג פרוטוקול “גרוע”, שעובד בסיבוכיות תקשורת \( O\left(\lg^{2}n\right) \). אחר כך נשפר אותו. “גרוע” במרכאות כי גם הסיבוכיות הזו היא נמוכה מאוד ביחס לחסם העליון הנאיבי (\( O\left(n\right) \)). הרעיון הוא שאליס ובוב יתחזקו, בנפרד, קבוצות של “מועמדים להיות החציון” שלהם - נסמן אותן ב-\( x^{\prime} \) וב-\( y^{\prime} \), ובהתחלה הן יכילו את כל \( x,y \). בכל סיבוב של הפרוטוקול אליס ובוב יצליחו, באמצעות שליחת הודעות כלשהי, לקצוץ בחצי את גודל קבוצות המועמדים. מה שהם ישלחו, בפשטות, יהיו החציונים הנוכחיים של \( x^{\prime} \) ו-\( y^{\prime} \). צריך \( \lg n \) ביטים בשביל לשלוח כל אחד מהם. בואו נניח שאליס שלחה את \( a \) ובוב שלח את \( b \) והם רואים ש-\( a<b \). מה עכשיו? ובכן, ברור שהחציון שאותו מחפשים נמצא אי שם בין \( a \) ל-\( b \), שכן אם מספר כלשהו קטן מ-\( a \) אז הוא לא גדול יותר מאשר מחצית מאברי \( x^{\prime} \), ובוודאי שאינו גדול יותר מאשר ממחצית מאברי \( y^{\prime} \) ולכן יגם ממחצית אברי האיחוד שלהם. באותו אופן מספר שגדול מ-\( b \) אינו יכול להיות החציון.

כעת, אליס תעיף מ-\( x^{\prime} \) מחצית מהאיברים - את הקטנים ביותר. בוב יעיף מ-\( y^{\prime} \) מחצית מהאיברים - הגדולים ביותר. מכיוון שאליס העיפה איברים שקטנים מהחציון האמיתי, ובוב העיף איברים שגדולים מהחציון האמיתי, והם העיפו את אותו מספר האיברים, אז החציון המקורי יהיה גם החציון של איחוד הקבוצות המקוצצות, שכעת גודלן הוא חצי ממה שהיה קודם.

אותו תעלול עושים אבל הפוך אם \( b<a \). אם \( a=b \) אז זהו בוודאי החציון, שכן לפני רגע אמרנו שהוא נמצא בין \( a \)ל-\( b \).

יש \( O\left(\lg n\right) \) סיבובים לפרוטוקול הזה ובכל אחד מהם כל אחד מהצדדים שולח מספר וזה דורש \( O\left(\lg n\right) \) ביטים. סך הכל נשלחים \( O\left(\lg^{2}n\right) \) ביטים, אבל זה לא מספיק לנו; אנחנו רוצים לשפר.

למרבה המזל, השיפור מאוד קל, ודורש רק אבחנה אחת, מקסימה, על אופן פעולתו של הפרוטוקול הזה. נשים לב שאליס ובוב לא באמת רוצים לדעת את \( a,b \) האחד של השני - רק לדעת מי מהם גדול יותר. כדי לדעת את זה, מספיק לשלוח את \( a,b \) ביט אחרי ביט, החל מהביט המשמעותי ביותר. כלומר - כל מספר מיוצג על ידי סדרה של בדיוק \( \lg n \) ביטים, וייתכן שחלק מהביטים המובילים הם 0 - הן אליס והן בוב מתחילים לשלוח ביטים החל מהשמאלי ביותר. כל עוד יש שוויון, הם ממשיכים לשלוח את הביט הבא; ברגע שאין שוויון הם יודעים בדיוק מי הגדול יותר (זה שהביט שלו היה 1).

כפי שכבר אמרנו, אחרי הקיצוץ שאליס ובוב מבצעים, האיברים היחידים ששורדים בקבוצות שלהם הם איברים שהם בין \( a \) ו-\( b \). בשלב של הקיצוץ אליס ובוב כבר מכירים חלק מהביטים של \( a \) ו-\( b \): כל הביטים המשמעותיים ביותר שעליהם \( a,b \) מסכימים. הפאנץ’ הסופי הוא שגם כל מי שבין \( a \) ו-\( b \) מסכים על אותם ביטים. אם \( a=0100 \) (הידוע בשמו הארצי “4”) ו-\( b=0111 \) (הידוע בשמו הארצי “7”), אז המספרים היחידים שביניהם הם \( 0101,0110 \) (5 ו-6) ושניהם מסכימים עם \( a,b \) על התחילית \( 01 \). מכאן שאין שום צורך לשלוח את הביטים הללו מחדש בסיבוב הבא של הפרוטוקול - אליס ובוב ימשיכו לשלוח ביטים החל מהספרה המעניינת הבאה.

מכיוון שכל מספר מיוצג על ידי \( \lg n \) ביטים, ואליס ובוב משווים פעם אחת בכל הפרוטוקול ביט עבור כל אחד מהמיקומים האפשריים, הם סך הכל מחליפים \( O\left(\lg n\right) \) ביטים, כנדרש.

הדוגמה הזו מראה עד כמה אפשר להיות מתוחכמים לפעמים בפתרון בעיות שנראות בלתי אפשריות לפתרון שאינו אלמנטרי. זו אולי ההמחשה הטובה ביותר לחיים הקשים שיש לחוקרי תורת הסיבוכיות; המטרה שלהם היא להראות חסמים תחתונים, כלומר שבעיה כלשהי אינה ניתנת לפתרון בסיבוכיות נמוכה, ולא משנה מה עושים. לשם כך הם צריכים איכשהו לטפל בכל הטריקים האפשריים “בו זמנית”, אבל בגלל שאפשר להשתמש בטריקים מאוד, מאוד מחוכמים, אין ממש סיכוי לתת טיעון שמקיף את כולם בצורה ישירה. לכן עיקר המאמץ מתמקד בשיטות כלליות וגנריות יותר שמראות חסמים תחתונים באופן שחומק מעיסוק בפרטים הספציפיים של פתרונות ספציפיים.

הרעיון הבסיסי בניתוח כללי של פרוטוקולים מהסוג שתיארתי למעלה הוא לחשוב עליהם כעץ, שבו בכל צומת או תורה של אליס לדבר, או תורו של בוב. כל אחד מהם אומר 0 או 1 כפונקציה של הקלט שלו עצמו ושל הצומת הנוכחי בעץ (כלומר, לצמתים שונים בעץ מתאימות פונקציות אחרות שאומרות להם איך לדבר). לצומת יש שני בנים - אחד שאליו עוברים אם נאמר 0, והשני שאליו עוברים אם נאמר 1. העלים של העץ מכילים את התוצאות של הפרוטוקול - לצורך פשטות נניח שמדובר רק על ביט בודד של תשובה.

האבחנה המרכזית כאן היא שאם על שני זוגות קלטים שונים \( \left(x_{1},y_{1}\right) \) ו-\( \left(x_{2},y_{2}\right) \) אליס ובוב מגיעים לאותו צומת בפרוטוקול, אז הם מגיעים לאותו הצומת גם עבור הזוג \( \left(x_{1},y_{2}\right) \). נסו להוכיח את הטענה הזו - דרך פשוטה אחת היא להוכיח באינדוקציה על עומק הצומת. האינטואיציה פה היא שאם על שני הזוגות המקוריים אליס ובוב הגיעו לאותו צומת בפרוטוקול, זה אומר שהתקשורת שנשלחה ביניהם הייתה זהה בשני המקרים, ולכן אליס לא יכולה להבדיל, באמצעות התקשורת שבוב שלח לה עד שהם הגיעו לצומת המדובר, בין זה שיש לו \( y_{1} \) וזה שיש לו \( y_{2} \), כל עוד התשובות שהיא עצמה נותנת מתאימות לקלט \( x_{1} \) או \( x_{2} \) שיש לה.

המסקנה מהטענה הזו היא שיש לאוסף התוצאות האפשריות של הפרוטוקול תכונה קומבינטורית לא טריוויאלית. חשבו על טבלה שבה השורות מיוצגות על ידי הערכים האפשריים של \( x \) והעמודות על פי הערכים האפשריים של \( y \) ובתא בטבלה המתאים לזוג \( \left(x,y\right) \) כלשהו יש ביט המתאים לפלט הפרוטוקול עבור \( \left(x,y\right) \). אז הטבלה ניתנת לחלוקה למלבנים כרומטיים - כלומר, מלבנים שכל אחד מהם בנפרד, או שכולו מסומן ב-0-ים, או שכולו מסומן ב-1-ים.

צריך להיות קצת זהירים עם השימוש במילה “מלבן” כאן, כי הכוונה אינה למלבן גאומטרי אלא להכללה שלו - מלבן קומבינטורי. במלבן גאומטרי כל השורות סמוכות זו לזו, אבל כאן זה לא הכרחי. פורמלית, אם יש לנו שתי קבוצות \( X,Y \) (חשבו עליהם כעל אוספי כל ה-\( x \)-ים וה-\( y \)-ים האפשריים) ויש לנו שתי תת קבוצות \( A\subseteq X \) ו-\( B\subseteq Y \), אז \( A\times B \) היא מלבן קומבינטורי, גם אם אברי \( A \) או \( B \) לא באים באופן רציף. הגדרה שקולה למלבן קומבינטורי הוא זו: קבוצה של זוגות \( \left(x,y\right) \) כך שאם \( \left(x_{1},y_{1}\right),\left(x_{2},y_{2}\right) \) שייכים לקבוצה, כך גם \( \left(x_{1},y_{2}\right) \) ו-\( \left(x_{2},y_{1}\right) \). נראה מוכר? זה בדיוק מה שהוכחו למעלה - שלכל צומת בפרוטקול, קבוצת “זוגות הקלטים שמביאות את אליס ובוב לצומת הזה” היא מלבן קומבינטורי.

נניח שלפרוטוקול יש \( t \) עלים - כלומר, יש בדיוק \( t \) מסלולים שונים מתחילת הפרוטוקול ועד סופו. כל עלה כזה מגדיר מלבן מונוכרומטי בתוך \( X\times Y \), ואיחוד כל המלבנים הללו הוא כל \( X\times Y \). לכן, אם נצליח להראות עבור \( f \) כלשהי שבכל חלוקה אפשרית של \( X\times Y \) למלבנים מונוכרומטיים (מונוכרומטיים ביחס ל-\( f \), כלומר בכל מלבן כזה \( f \) נותנת את אותו ערך לכל אברי המלבן) יש לפחות \( t \) מלבנים, הראינו שבעץ הפרוטקול חייבים להיות לפחות \( t \) עלים. מכיוון שזהו עץ בינארי (לכל צומת יש בדיוק שני בנים), זה מניב חסם תחתון כלשהו על עומק העץ - הוא חייב להיות לפחות \( \lg t \). זה, בתורו, מניב חסם תחתון על סיבוכיות התקשורת של הפרוטוקול, כי עומק העץ הוא כמספר הביטים שמוחלפים במהלך ריצת הפרוטוקול.

סיכום: אם עבור \( f \) נראה שכל נסיון לפרק את \( X\times Y \) למלבנים מונוכרומטיים ביחס ל-\( f \) דורש המון מלבנים, הראינו חסם תחתון גדול על סיבוכיות התקשורת של \( f \).

זה מוביל אותנו לשיטה האלמנטרית ביותר למציאת חסמים תחתונים - שיטת ה-Fooling Set. כשלמדתי את הקורס בנושא בדיחה ידועה הייתה למצוא תרגומים מגוחכים למונח הזה - “קבוצה היתולית” ו”קבוצה קרקסית” היו חלק מההצעות. לדעתי “קבוצה משטה” היא התרגום המתאים ביותר, ובו אשתמש. הרעיון בקבוצה משטה הוא פשוט - אם נצליח למצוא קבוצה של קלטים \( A \) כך שלכל \( \left(x,y\right)\in A \) מתקיים \( f\left(x,y\right)=1 \) (כאשר \( f \) היא הפונקציה שאנו מנסים למצוא לה חסם תחתון) אבל לכל \( \left(x_{1},y_{1}\right),\left(x_{2},y_{2}\right)\in A \) מתקיים ש-\( f\left(x_{1},y_{2}\right)=0 \) או \( f\left(x_{2},y_{1}\right)=0 \), אז בהכרח כל זוג \( \left(x,y\right)\in A \) חייב לשכון במלבן מונוכרומטי אחר, בכל חלוקה אפשרית של \( X\times Y \) למלבנים מונוכרומטיים (כי אם \( \left(x_{1},y_{1}\right),\left(x_{2},y_{2}\right) \) שוכנים באותו המלבן, כך גם \( \left(x_{1},y_{2}\right) \) ו-\( \left(x_{2},y_{1}\right) \) ואחד מהם הוא בעל ה”צבע” הלא נכון). אותו הדבר עובד, כמובן, גם אם דורשים שכל אברי \( A \) יחזירו 0. לכן בכל חלוקה של \( X\times Y \) למלבנים מונוכרומטיים יש לפחות \( \left|A\right| \) מלבנים ולכן \( \lg\left|A\right| \) הוא חסם תחתון על סיבוכיות התקשורת של \( f \).

דוגמה? נניח ש-\( f \) היא פונקצית השוויון: \( \mbox{EQ}\left(x,y\right)=1 \) אם ורק אם \( x=y \). אז \( A=\left\{ \left(x,y\right)|x=y\right\} \) היא כמובן קבוצה משטה; מצד אחד \( f\left(x,y\right)=1 \) לכל \( \left(x,y\right)\in A \), ומצד שני \( f\left(x_{1},y_{2}\right)=0 \) כאשר \( x_{1}\ne y_{2} \). מה גודל \( A \)? ובכן, האיברים מיוצגים בעזרת \( n \) ביטים, ולכן יש \( 2^{n} \) ערכים אפשריים של \( x \), ולכן של איברים ל-\( A \), כלומר \( \left|A\right|=2^{n} \), כלומר החסם התחתון על סיבוכיות התקשורת שאותו מקבלים הוא \( \lg\left|A\right|=n \) - וחסם תחתון של \( \Omega\left(n\right) \) הוא אופטימלי למדי בפונקציות שמחזירות רק ביט בודד (כי בוב יכול פשוט לשלוח לאליס את כל הביטים שלו ואליס תבצע את החישוב ותשלח לו בחזרה את ביט הפלט של \( f \) כדי שגם הוא יידע). זה מראה מייד ש-\( \mbox{EQ} \) היא מאותן פונקציות שהכרחי לשלוח את כל המידע כדי לחשב אותן במשותף. אותו תעלול מראה חסם תחתון של \( \Omega\left(n\right) \) גם על הפונקציה הבאה: אם \( A,B \) הן שתי תת קבוצות של \( \left\{ 1,\dots,n\right\} \), אז \( f\left(A,B\right)=1 \) אם שתי הקבוצות נחתכות. במקרה זה הקבוצה המשטה היא אוסף כל הזוגות \( \left(A,\overline{A}\right) \) (\( \overline{A} \) הוא המשלים של \( A \) - כל האיברים האפשריים מהתחום שאינם ב-\( A \)).

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