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

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

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

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

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

בהישג יד?

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

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

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

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

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

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

החומר של סיוטים

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

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

אז ליפטון הוכיח הוא יכול לבנות מערכת של גודל n שבו הנתיב הקצר ביותר בין שני מצבים כלל יותר ממעברי $latex 2^{2^n}$. זה מרמז על גבול תחתון אקספוננציאלי כפול מקביל למאמץ הנדרש כדי לקבוע את הנגישות במערכות שלו. זה היה תגלית מדהימה - צמיחה מעריכית כפולה היא חומר הסיוטים של מדעני המחשב. ואכן, חוקרים לעתים קרובות נרתעים אפילו מצמיחה אקספוננציאלית רגילה, שמחווירה בהשוואה: $latex {2^5}= 32$, אבל $latex 2^{2^5}$ הוא יותר מ-4 מיליארד דולר.

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

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

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

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

מגדל של כוחות

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

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

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

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

קשה לעטוף את הראש כמה מהר הטטרציה יוצאת מכלל שליטה: $latex 2 uparrowuparrow 3$, או $latex 2^{2^2}$, הוא 16, $latex 2 uparrowuparrow 4$ הוא קצת יותר מ-65,000, ו $latex 2 uparrowuparrow 5$ הוא מספר עם כמעט 20,000 ספרות. זה בלתי אפשרי פיזית לרשום את כל הספרות של $latex 2 uparrowuparrow 6$ - אחריות של חיים ביקום כל כך קטן.

בתוצאה המובהקת שלהם, צ'רווינסקי ועמיתיו הוכיחו שקיימות מערכות חיבור וקטוריות בגודל n כאשר הדרך הטובה ביותר לקבוע את הנגישות היא למפות נתיב הכולל יותר ממעברי $latex 2 uparrowuparrow n$, מה שמרמז על גבול תחתון חדש שהתגמד את זה של ליפטון. אבל עד כמה שהטטרציה היא סחרחרת, זו עדיין לא הייתה המילה האחרונה על מורכבות הבעיה.

לקווינקווינטיליון ומעבר לו 

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

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

פונקציית אקרמן, המסומנת $latex A(n)$, היא מה שאתה מקבל כשאתה עובר שלב אחד במעלה סולם הפעולות הזה עם כל עצירה על קו המספרים: $latex A(1) = 1 + 1$, $latex A (2) = 2 × 2$, $latex A(3) = 3^3$, $latex A(4)=4 uparrowuparrow 4=4^{4^{4^4}}$, וכן הלאה. מספר הספרות ב-$latex A(4)$ הוא בעצמו מספר ענק השווה בערך ל-1 quinquagintillion - זה השם הגחמני והדרוש רק לעתים נדירות עבור 1 ואחריו 153 אפסים. "אל תדאג לגבי אקרמן מ-5," ייעץ חוויאר אספרזה, מדען מחשבים באוניברסיטה הטכנית של מינכן.

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

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

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

מעולם לא הסתיים

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

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

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

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

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

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