בכתבה הזו
OpenAI הודיעה שמודל פנימי שלה הפריך את ההשערה האקספוננציאלית (Exponential Time Hypothesis, או ETH), השערה מרכזית בתורת הסיבוכיות, התחום שחוקר כמה זמן וזיכרון דרושים כדי לפתור בעיות חישוביות. לפי הודעת החברה, ההפרכה נמצאה ב-16 באוקטובר 2026 ואומתה בכלי Lean יום לאחר מכן. בינתיים מדובר בטענה של OpenAI עצמה, ואיש מחוץ לחברה עוד לא פרסם הערכה בלתי תלויה.
מהי ההשערה ולמה היא חשובה
ETH עוסקת בבעיית הסיפוקיות של נוסחאות בוליאניות: האם אפשר לבחור ערכי אמת ושקר למשתנים כך שנוסחה לוגית תתקיים. הבעיה קשורה עמוקות לשאלה המפורסמת P מול NP. לפי ההשערה, אין דרך לפתור אותה בזמן תת-אקספוננציאלי, כלומר הרבה מהר יותר מניסיון גס של כל האפשרויות. לפי OpenAI, רבים האמינו שההשערה נכונה, והיא שימשה במאות מאמרים להסקת תוצאות קושי מותנות בתחומים כמו תורת הגרפים, ביולוגיה חישובית, מסדי נתונים וגיאומטריה חישובית.
OpenAI כותבת שההפרכה "פותחת מחדש שאלות" לגבי מידת ההאצה האפשרית במשימות האלה, ואולי תכוון חיפוש אחר אלגוריתמים טובים יותר. החברה מדגישה שמציאת אלגוריתמים כאלה והפיכת ההתקדמות התאורטית לשיפור מעשי ידרשו מחקר נוסף רב.
מה כתוב במסמכי ה-Lean
במאגר GitHub של OpenAI יש מסמך שמתאר את היקף ההוכחה הפורמלית. לפי המסמך, Lean מוכיח שעבור k קבוע, מכונה דטרמיניסטית סופרת במדויק השמות מספקות של נוסחת k-CNF עם n משתנים בזמן תת-אקספוננציאלי ובזיכרון פולינומי. Lean הוא כלי שבודק הוכחות מתמטיות צעד אחר צעד.
הקבוצה שתבדוק
OpenAI ביקשה ממומחים חיצוניים לארגן קבוצות שיסבירו את התוצאות. את העבודה על ETH ירכזו ויאמתו ראסל אימפליאצו ורמאמוהאן פאטורי מאוניברסיטת קליפורניה בסן דייגו, וריאן וויליאמס מ-MIT. אימפליאצו ופאטורי, יחד עם פרנסיס זיין, הם מנסחי ההשערה המקוריים. וויליאמס הפריך בעבר גרסאות חזקות שלה. וויליאמס כתב ב-X שמודל פנימי של OpenAI הפיק "הפרכה נטענת" של ETH, ושהוא ושני עמיתיו התבקשו לסייע בארגון בדיקה פתוחה ועצמאית של הטענה.
לפי OpenAI, הקבוצה ביקשה שכל הנתונים הגולמיים יפורסמו, והחברה הסכימה. היא גם התחייבה לממן כנס שיבחן את משמעות התוצאה. ההוכחה בשפה טבעית וההוכחה ב-Lean כבר פורסמו במאגר הציבורי שלה. החברה מבהירה שחברי הקבוצה פועלים באופן עצמאי, בלי הסכמי סודיות, בלי תשלום, ואינם מדברים בשמה. היא גם אומרת שאינה מבקשת קרדיט אקדמי על התגליות.
עוד שתי תוצאות באותה הודעה
ETH היא רק אחת משלוש תוצאות שהוכרזו. באנליזה הרמונית, לפי OpenAI, המודלים הוכיחו את השערת ההחלקה המקומית בכל מימד, ומכאן גם את השערת קקייה וההשערה של שטיין. בפיזיקה היא טוענת להוכחת קיום מתמטית קפדנית של תורות שדה קוונטיות מסוימות, כולל QCD. כתת-בעיה בעבודה נכללת גם הוכחת הקיום של תורת ינג-מילס הטהורה, שהיא חלק מאחת מבעיות פרס המילניום. בפיזיקה הקבוצה בראשות דיוויד גרוס החליטה לא לפרסם בינתיים את החומר שהפיק ה-AI ולכתוב אותו בעצמה.
לפי המאגר של OpenAI, רוב רובן של התוצאות הושגו באותו הליך קבוע עם מודל פנימי שלא שוחרר, למעט חריגים להליך, ובהם עבודה על אזור חסר אפסים של פונקציית זטא של רימן והוכחה של השערת הודג' למשפחה מסוימת של יריעות. המאגר גם מציין שחלק מהתוצאות לא עברו פורמליזציה ועלולות להכיל בעיות.
מה עוד לא ידוע
הקבוצה החיצונית טרם פרסמה הערכה. לא ידוע אם ההוכחה תעמוד בבדיקת מומחים. עד שזה יתברר, ההפרכה נשארת טענה של OpenAI.
תגובות