המסע בן 50 השנים של תורת המורכבות אל גבולות הידע | מגזין קוונטה

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

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

"ב-100% לא הבנתי", אמר קרמוסינו. "אבל ידעתי שאני רוצה".

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

למרות עשרות שנים של מאמצים של חוקרים בתחום תיאוריית המורכבות החישובית - חקר שאלות כאלה על הקושי הפנימי של בעיות שונות - פתרון לשאלת P לעומת NP נותר חמקמק. ואפילו לא ברור היכן צריכה להתחיל הוכחה.

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

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

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

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

"התברר שמטה-מורכבות קרובה ללב העניינים", אמר סקוט אהרונסון, תיאורטיקן של מורכבות באוניברסיטת טקסס, אוסטין.

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

ידועים אלמונים

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

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

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

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

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

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

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

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

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

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

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

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

נתיבים שונים

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

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

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

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

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

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

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

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

אוניברסלי קשה

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

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

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

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

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

הסדרת הקושי של כל בעיה מלאה ב-NP תספיק כדי לפתור את שאלת P לעומת NP. אם P ≠ NP, ההבחנה בין בעיות קלות וקשות מתקיימת על ידי אלפי עמודות שכולם חזקים באותה מידה. אם P = NP, הבניין כולו מתנודד על סף קריסה, רק מחכה שחתיכה בודדת תיפול.

קוק, לוין וקרפ איחדו מה שנראה כמו בעיות רבות שאינן קשורות. כעת כל מה שתורת המורכבות היה צריך לעשות היה לפתור בעיה אחת: האם P = NP או לא?

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

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

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

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

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

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

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

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

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

"תורת המורכבות מקוללת ומבורכת בכל כך הרבה מחסומים", אמר אילנגו.

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

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

שביל סובב

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

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

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

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

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

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

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

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

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

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

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

"פשוט אין מספיק מעגלים קטנים להסתובב," אמר אהרונסון.

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

Crypto Bros

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

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

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

"פשוט היה לי מזל שלא ידעתי עד כמה הבעיה הזו קשה", אמר רזבורוב. "אחרת אולי אפילו לא הייתי מתחיל".

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

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

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

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

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

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

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

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

בדיחה אכזרית

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

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

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

"אתה כמעט לא יכול שלא לקבל יותר ממה שהתמצית", אמר קרמוסינו.

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

כדי להבין את הקשר הזה, דמיינו לעצמכם מסתכלים בעמודת הפלט בטבלת האמת של פונקציה בוליאנית עם משתני קלט רבים ומחליפים כל "true" ב-1 וכל "false" ב-0:

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

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

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

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

אל המטאברס

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

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

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

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

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

המאמר של Kabanets ו-Cai הדגיש בעיה חישובית המובלעת בניסוח של Razborov ו-Rudich של מחסום ההוכחות הטבעיות: בהתחשב בטבלת האמת של פונקציה בוליאנית, קבע אם יש לה מורכבות מעגל גבוהה או נמוכה. הם כינו זאת בעיית גודל המעגל המינימלי, או MCSP.

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

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

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

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

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

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

"זוהי, במובן מסוים, מטא-מטה-מורכבות," אמר Rahul Santhanam, תיאורטיקן של מורכבות באוניברסיטת אוקספורד.

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

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

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

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

מלחמת העולמות

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

"הוא הציק לאנשים בצורה טובה", נזכר קבאנטס.

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

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

"זה לא היה מובן מאליו שקשר כזה יתקיים בכלל", אמר אימפאליאצו.

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

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

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

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

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

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

קרדיט חלקי

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

"דברים חדשים קורים", אמר קולוקולובה. "יש הרבה חוקרים זוטרים ממש ממש מבריקים."

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

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

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

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

"זו באמת תהיה תוצאה מרעישה", אמר סנת'נם.

הוכחה ש-MCSP הוא NP-שלם עשוי להיראות כמו משימה קשה - אחרי הכל, השאלה פתוחה כבר למעלה מ-50 שנה. אבל אחרי א פריצת דרך בשנה שעברה מאת Hirahara, החוקרים עכשיו הרבה יותר קרובים ממה שמישהו היה מצפה לפני כמה שנים.

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

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

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

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

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

החתיכות החסרות

MCSP היא אפילו לא בעיית המטא-מורכבות היחידה שגררה פריצת דרך גדולה. בשנת 2020, הקריפטוגרף של קורנל טק מעבר רפאל והתלמיד שלו לתואר שני יאני ליו גילה קשר בין בעיית מטא-מורכבות שונה לבין פרוטוקול קריפטוגרפי בסיסי המגדיר את הגבול בין היוריסטיקה לפסילנד, הגרוע ביותר בעולמות של אימפגליאצ'ו (שבו בעיות של NP-שלמות הן קשות במובן המקרה הממוצע, אבל הצפנה עדיין בלתי אפשרית). זה הופך את הבעיה שהם למדו למועמד מוביל להתקפה על פסילנד, ושלהם עבודה עדכנית יותר מציין שזה יכול לעבוד גם נגד Heuristica.

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

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

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

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

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

"זה בעצם די נהדר שזה כל כך קשה," אמר קרמוסינו. "לעולם לא אהיה משועמם."

הערת העורך: סקוט אהרונסון הוא חבר ב מגזין Quanta"S ועדת ייעוץ.