המספר 15 מתאר את הגבול הסודי של רשת אינסופית

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

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

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

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

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

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

כל דרך אפשרית

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

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

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

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

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

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

לאחר ש-Subercaseaux התחיל ב-CMU ושכנע את Heule לעבוד איתו, הם מצאו במהירות דרך לכסות את הרשת עם 15 מספרים. הם גם הצליחו לשלול את האפשרות לפתור את הבעיה עם 12 מספרים בלבד. אבל רגשות הניצחון שלהם היו קצרי מועד, שכן הם הבינו שהם בסך הכל שיחזרו תוצאות שהיו בסביבה זמן רב: כבר ב-2017, החוקרים ידעו שהתשובה היא לא פחות מ-13 או יותר מ-15 .

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

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

"ברגע שהבנו שיש 20 שנות עבודה על הבעיה, זה שינה לחלוטין את התמונה", אמר.

הימנעות מהוולגרי

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

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

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

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

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

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

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

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

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

Heule ו-Subercaseaux הוסיפו כללים שאפשרו למחשב להתייחס לשילובים סימטריים כשווים, והקטינו את זמן החיפוש הכולל בפקטור של שמונה. הם גם השתמשו בטכניקה שפיתח Heule בעבודה קודמת שנקראת cube and conquer, שאפשרה להם לבדוק שילובים נוספים במקביל זה לזה. אם אתה יודע שתא נתון חייב להכיל 3, 5 או 7, אתה יכול לפצל את הבעיה ולבדוק כל אחת משלוש האפשרויות בו-זמנית על קבוצות שונות של מחשבים.

עד ינואר 2022 שיפורים אלה אפשרו ל-Heule ול-Subercaseaux לשלול 13 כתשובה לבעיית צביעת האריזה בניסוי שדרש פחות מיומיים של זמן חישוב. זה הותיר אותם עם שתי תשובות אפשריות: 14 או 15.

פלוס גדול

כדי לשלול 14 - ולפתור את הבעיה - Heule ו-Subercaseaux היו צריכים למצוא דרכים נוספות להאיץ את החיפוש במחשב.

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

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

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

בסיוע היעילות של חיפוש הפלוס, Heule ו-Subercaseaux שללו 14 בניסוי מחשב בנובמבר 2022 שבסופו של דבר לקח פחות זמן לרוץ מזה שהשתמשו בו כדי לשלול 13. הם בילו את ארבעת החודשים הבאים כדי לאמת את זה המסקנה של המחשב הייתה נכונה - כמעט זמן כמו שהם השקיעו כדי לאפשר למחשב להגיע למסקנה הזו מלכתחילה.

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

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

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