המתמטיקה של המחשב

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

 פנחס ויגדרזון אהב לפתור חידות ולאתגר באמצעותן את בנו הבכור, אבי, שנקרא על שם סבו אברהם. למעשה כל חייו מאז ועד היום, אבי ויגדרזון מנסה לפתור חידות, ואת חלקן הוא גם הצליח. הוא כל כך הצליח, עד שהוא אחד החוקרים המעוטרים בעולם במתמטיקה ובמדעי המחשב. לפני שלוש שנים זכה בפרס אבל במתמטיקה, ובשבוע שעבר הוכרז כי יקבל השנה את פרס טיורינג, הפרס היוקרתי ביותר במדעי המחשב. שני הפרסים נחשבים לעיתים מקבילים לפרס נובל, שאינו מוענק בתחומים אלה. רשימת הישגיו כוללת גם את פרס נבלינה (1994), פרס גדל (2009) ופרס קנות (2019).

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

האדם הראשון שמקבל גם פרס טיורינג וגם פרס אבל, לצד פרסים רבים נוספים. אבי ויגדרזון בלונדון, 2012 | צילום: Ednawig, ויקיפדיה

מחיפה לפרינסטון

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

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

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

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

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

מדעי המחשב כיישום מעשי של מתמטיקה. כיום אבטחת מידע היא ענף חשוב מאוד בתחום שהיה בחיתוליו בתקופת לימודיו של ויגדרזון. אבטחה ממוחשבת של מסחר מקוון | איור: VectorManZone, Shutterstock

חיים סיבוכיים

ויגדרזון השלים את לימודי התואר השני בפרינסטון בהנחייתו של ריצ'רד ליפטון (Lipton), שהיה אז אחד משני התאורטיקנים היחידים בתחום מדעי המחשב במוסד הזה. מיד לאחר השלמת התואר המשיך לדוקטורט בהדרכתו. "ליפטון עסק בסיבוכיות", סיפר לימים ויגדרזון. "הוא איש עם יצירתיות מדהימה ותחומי עניין רחבים, כך שהחלפנו יחד תחומי מחקר. עברתי יחד איתו ולמדתי נושאים מגוונים [...] יתכן שממנו קיבלתי את החיידק של חשיבה על בעיות מתמטיות במחשוב…". 

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

 לאחר השלמת הדוקטורט, עשה ויגדרזון השתלמות פוסט-דוקטורט בחברת IBM ובאוניברסיטת קליפורניה בברקלי, שם עבד לצדו של ריצ'רד קרפ (Karp), לימים חתן פרס טיורינג בעצמו. בשובו לארץ ב-1986 התמנה למרצה בכיר באוניברסיטה העברית בירושלים, שם התקדם במהרה בסולם הדרגות האקדמי ובמחצית שנות ה-90 מונה לראש המכון למדעי המחשב. בין לבין, הוא שהה כחוקר אורח במכון למחקרים מתקדמים בפרינסטון, אחד ממכוני המחקר היוקרתיים בתבל. ב-1999 הצטרף אליו כחוקר מן המניין, הישראלי השני אי פעם שהחזיק במשרה שם (אחרי הפיזיקאי נתי זייברג). כעבור שנים אחדות  עזב את ירושלים וקבע את מקום מושבו האקדמי בפרינסטון באופן בלעדי.

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

ידיעה אפסית ואקראיות מדומה

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

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

גולדווסר יחד עם סילביו מיקאלי (Micali) וצ'ארלס ראקוף ( Rackoff) הציעו ב-1985 את הרעיון של הוכחה באפס ידיעה, שהוא יסוד מרכזי בקריפטוגרפיה בת זמננו. בדיאלוג בין שני צדדים, צד אחד יכול לשכנע את הצד השני שטענה מסוימת נכונה בסבירות גבוהה, בלי לחשוף שום פרט לגבי הטענה עצמה.

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

ויגדרזון, עם מיקאלי ועודד גולדרייך, לימים חתן פרס ישראל בתחום חקר המתמטיקה ומדעי המחשב, הראה כי כל בעיות NP ניתנות להוכחה באפס ידיעה. בהסבר פשוט, בעיות Nondeterministic polynomial, או בקיצור NP, הן בעיות שאפשר לוודא במהירות שיש להן פתרון, גם אם למצוא את הפתרון עצמו לוקח זמן רב מאוד. בלי קשר ישיר לעניין, מחלקה אחרת של בעיות, המכונות polynomial ומסומנות באות P, הן בעיות שזמן ההרצת התוכנה או האלגוריתם לפתרונן קצר יחסית. בעיה עיקרית ופתוחה במדעי המחשב שואלת אם P=NP, כלומר האם כל בעיה שניתן לוודא במהירות שיש לה פתרון, היא גם בעיה שניתן למצוא במהירות את פתרונה?

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

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

אפשר להראות לצד השני שאתה יודע את הפתרון, בלי לרמוז לו מה הפתרון. הוכחה באפס ידיעה | איור: Crystal Eye Studio, Shutterstock

חסמים תחתונים

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

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

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