תאר לעצמך שאתה בחיפוש אחר להבין את עצם טבעו של החישוב. אתה עמוק במדבר, רחוק מכל נתיב, ו בלתי ניתן לבירור הודעות חצובים בגזעי העצים מסביבך - BPP, AC⁰[מ], Σ₂P, YACC ומאות אחרים. הגליפים מנסים לומר לך משהו, אבל מאיפה להתחיל? אתה אפילו לא יכול לשמור על כולם ישרים.

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

בשנות השמונים והתשעים של המאה ה-1980, אימפגליאצו מילאה תפקיד מוביל באיחוד יסודות תיאורטיים של קריפטוגרפיה. ב-1995, הוא ניסח את המשמעות של ההתפתחויות החדשות הללו במאמר איקוני שניסח מחדש פתרונות אפשריים ל-P מול NP וקומץ בעיות קשורות בשפה של חמישה עולמות היפותטיים אנו עשויים להתגורר, המכונים בגחמה אלגוריתמיקה, היוריסטיקה, פסילנד, מיניקריפט וקריפטומניה. חמשת העולמות של Impagliazzo היוו השראה לדור של חוקרים, והם ממשיכים להנחות את המחקר בתת-התחום הפורח של מטא-מורכבות.

ואלה לא העולמות היחידים שהוא חלם. Impagliazzo היה חובב כל חייו של משחקי תפקידים שולחניים כמו מבוכים ודרקונים, והוא נהנה להמציא מערכות חוקים חדשות והגדרות חדשות לחקור. אותה רוח שובבה מחייה את תרגול 30 השנים שלו בקומדיה אלתור.

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

Quanta דיבר עם Impagliazzo על ההבדל בין בעיות קשות לחידות קשות, התייעצות עם אורקלים, והשיעורים המתמטיים של קומדיה אלתורים. הראיון תמצה ונערך למען הבהירות.

מתי התעניינת לראשונה במתמטיקה?

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

מה עם מדעי המחשב? חלקים מהתחום מאוד מופשטים, אבל הם לא מה שרוב האנשים נתקלים בו לראשונה.

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

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

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

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

מה ההבדל בין בעיה לפאזל?

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

ההבדל בין חמשת העולמות הוא איך הם עונים על השאלות "האם יש בעיות קשות?" ו"האם יש חידות קשות?"

כיצד מתרחשות התשובות השונות הללו?

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

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

מה הניע אותך לכתוב את מאמר חמשת העולמות?

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

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

אז למה למסגר את זה ככה, כעולמות שונים עם שמות מוזרים?

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

האם החוקרים שללו כל אחד מחמשת העולמות האפשריים?

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

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

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

האם החוקרים חושבים שקופסאות הקסם הללו באמת יכולות להתקיים?

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

גילית גם קשרים בין קשיות חישוב לאקראיות. איך החיבור הזה עובד?

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

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

אז התובנה היא שבעיות קשות שאת פתרונותיהן איננו יודעים יכולות לספק מקור למספרים "פסאודורנדומליים" שנראים אקראיים.

אם כבר מדברים על מונטי פייתון, אני יודע שאתה עושה קומדיית אלתור כבר הרבה זמן - איך התחלת?

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

מה היא חשבה?

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

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

האם ביצוע אלתור שינה את הדרך שבה אתה ניגש למחקר שלך?

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

כמו מה?

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

מה לגבי האהבה שלך למשחקי תפקידים - האם זה השפיע על העבודה שלך בכלל?

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

מדוע משחקי תפקידים הם דרך כה משכנעת לחקור עולמות היפותטיים?

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