OpenAI טוענת להפרכת השערת ETH: מה עדיין דורש בדיקה
OpenAI הודיעה כי מודליה הפריכו את השערת הזמן האקספוננציאלי ופרסמה הוכחות ב־Lean. הטענה טרם זכתה לקונצנזוס מדעי; אימותה עשוי לשנות את הבנת הקושי החישובי.
OpenAI הודיעה ב־26 באוקטובר 2026 כי מודליה הפריכו את השערת הזמן האקספוננציאלי, ETH, אחת ההשערות שעליהן נשענות טענות רבות על גבולות היעילות של אלגוריתמים. החברה פרסמה תוצרים והוכחות פורמליות ב־Lean במסגרת ההכרזה, אך נכון ל־27 באוקטובר מדובר בטענה מחקרית שנמסרה לבחינה, לא בתוצאה שכבר זכתה לקונצנזוס מדעי. אם תאומת, משמעותה תהיה קודם כול שינוי בהבנת הקושי החישובי, ולא הבטחה שמחשבים יפתרו מחר כל בעיה קשה.
מה OpenAI פרסמה, ומה עדיין בגדר טענה
הטענה להפרכת ETH היא חלק מהודעה רחבה על שלושה הישגים שלדברי OpenAI הפיקו מודליה. השניים האחרים הם הוכחת השערת ההחלקה המקומית, שממנה נובעות גם תוצאות על השערת קקייה בכל הממדים, והוכחות קיום לתורות שדה קוונטיות, ובהן QCD. אלה תחומים שונים, ולכן אין לראות באישור עתידי של אחת התוצאות אישור אוטומטי של האחרות.
לפי הודעת החברה, התוצרים וההוכחות הפורמליות בתחומי המתמטיקה ומדעי המחשב פורסמו, והוקמו שיתופי פעולה עם חוקרים חיצוניים לבחינת התוצאות ולהסברתן. חומרי הפיזיקה עדיין אינם פומביים. ההבחנה חשובה: היכולת לעיין בטיעון, לבדוק את הנחותיו ולשחזר את האימות שלו היא חלק מרכזי בהערכת הטענה, ולא פרט טכני שנלווה להכרזה.
במקרה של ETH, השאלה אינה רק אם המודל הפיק מסמך שנראה כמו הוכחה. צריך להבין מה בדיוק נטען בו, לאיזו הגדרה של הבעיה הוא מתייחס, ואיך נובע ממנו חסם זמן הריצה. התחקיר שסופק אינו מפרט את האלגוריתם או את החסם המדויק, ולכן אין בסיס להציג כאן מנגנון הפרכה או להעריך את ביצועיו.
מהי ETH, ולמה הפרכתה אינה פתרון של P מול NP
ETH עוסקת בקצב הגידול של זמן החישוב הנדרש לפתרון בעיית 3-SAT. בבעיה הזאת מקבלים נוסחה לוגית המורכבת מתנאים על משתנים שערכם אמת או שקר, ובכל תנאי מופיעים שלושה ליטרלים, כלומר משתנים או שלילתם. המשימה היא לקבוע אם קיימת הצבת ערכים שמקיימת את כל התנאים יחד.
באופן לא פורמלי, ההשערה אומרת שאי אפשר לפתור את כל המקרים של הבעיה בזמן תת־אקספוננציאלי במספר המשתנים. אין פירוש הדבר שכל מקרה קשה: מופעים מסוימים יכולים להיות קלים מאוד. הטענה נוגעת לאלגוריתם כללי ולביצועיו במקרה הגרוע, כאשר גודל הקלט הולך וגדל.
החשיבות של ETH חורגת מ־3-SAT. באמצעות רדוקציות, חוקרים מקשרים בין בעיות ומשתמשים בהשערה כדי לטעון שאלגוריתמים בעלי קצבי ריצה מסוימים אינם אפשריים, בהנחה שהיא נכונה. אם ETH תופרך, המסקנות המותנות בה לא יהפכו אוטומטית לשגויות, אבל יהיה צורך בבסיס אחר כדי לבסס אותן. גם ההוכחות המקוריות לקשר המותנה יישארו תקפות.
הפרכת ETH אינה מוכיחה כשלעצמה ש־P=NP. זמן תת־אקספוננציאלי אינו בהכרח זמן פולינומי, ואלגוריתם בעל יתרון תאורטי עשוי עדיין להיות איטי מכדי לשמש ביישום מעשי.
מה Lean יכולה לבדוק, ומה נשאר לחוקרים
Lean היא מערכת להוכחות פורמליות: במקום להסתפק בטיעון בשפה טבעית, מנסחים הגדרות וטענות בשפה שהמערכת יכולה לבדוק לפי כללי ההיסק שלה. זהו יתרון משמעותי כשעוסקים בטיעונים ארוכים, משום שבדיקה פורמלית יכולה לחשוף פערים שקשה לאתר בקריאה רגילה. עם זאת, עצם הפרסום של קובצי הוכחה אינו תחליף לעיון בתוכנם.
הבדיקה המחקרית צריכה לחבר בין המשפט הפורמלי לבין הכותרת המדעית. הוכחה יכולה להיות תקינה ביחס להנחות שנכתבו, אך עדיין לדרוש בירור אם ההנחות וההגדרות תואמות בדיוק את ההשערה המקובלת. במקרה של טענה על זמן ריצה, חשוב במיוחד לבדוק את מודל החישוב, את מדד גודל הקלט ואת כל שלבי הניתוח.
- לזהות את הניסוח המדויק של ETH שההוכחה מתייחסת אליו ואת ההנחות שעליהן היא נשענת.
- לבדוק שהמשפט הפורמלי מכסה גם את נכונות הפתרון וגם את טענת הסיבוכיות הרלוונטית.
- לשחזר את בדיקת קובצי Lean ולבחון את התלויות והאקסיומות שבהם נעשה שימוש.
- להפריד בין אימות ההוכחה לבין השאלה אם אפשר לממש אלגוריתם שימושי על בסיס התוצאה.
הוכחה פורמלית בודקת שהמסקנה נובעת מההנחות שנוסחו. הבדיקה המדעית צריכה לוודא שזה אכן המשפט שעליו הוכרז.
המשמעות לישראל: מחקר תחילה, מוצר בהמשך
לקבוצות מחקר בישראל העוסקות באלגוריתמים ובסיבוכיות, השאלה המיידית היא אילו תוצאות בתחום שלהן נשענות על ETH. אם הטענה תאומת, יהיה מקום לחזור לחסמים מותנים, לבדוק אילו מהם תלויים בה ישירות ואילו נשענים על הנחות אחרות. זו עבודת מחקר ממוקדת, לא מחיקה גורפת של ספרות קיימת.
בחברות ישראליות שעוסקות באופטימיזציה, בתכנון מסלולים או באימות חומרה ותוכנה, נכון לבחון בהמשך אם הרעיונות החדשים ניתנים להעברה לבעיות שהמוצר באמת פותר. מדידה רלוונטית תצטרך להשתמש בקלטים מייצגים, בתקציב זיכרון מציאותי ובזמן ריצה בפועל. חסם תאורטי לבדו אינו מצדיק החלפת תשתית או התחייבות ללקוח על שיפור ביצועים.
גם לצוותי סייבר אין בסיס להסיק מההכרזה לבדה שהצפנה מסוימת נשברה. נדרשים קשר מתמטי מפורש לבעיה הקריפטוגרפית הרלוונטית וניתוח של עלות התקיפה. ההבחנה בין תוצאה בסיבוכיות לבין יכולת מעשית חשובה במיוחד כשמתרגמים חדשות מחקר להחלטות עסקיות.
מה צריך לקרות לפני שאפשר לדבר על פריצת דרך מאומתת
השלב הבא הוא בחינה עצמאית של החומרים: שחזור האימות, הסבר נגיש של הרעיון המרכזי ובירור מדויק של ההשלכות. שיתוף הפעולה שעליו הודיעה OpenAI מאפשר בחינה כזאת, אך אינו מעיד מראש על מסקנותיה. גם החברה מציינת שתרגום התוצאה לאלגוריתמים שימושיים דורש מחקר נוסף.
לכן נכון לעקוב אחרי שתי שאלות נפרדות: האם ההפרכה תקפה, ואם כן, מה ניתן לבנות ממנה. תשובה חיובית לראשונה תהיה משמעותית גם בלי שיפור מיידי בתוכנה מסחרית. עד שהבדיקה תתבהר, הסיפור הוא טענה יוצאת דופן עם חומרים לבחינה, ולא הכרזה שגבולות החישוב כבר הוסרו.
שאלות נפוצות
מהי השערת הזמן האקספוננציאלי ETH?
ETH היא השערה בתורת הסיבוכיות שלפיה אין אלגוריתם שפותר את כל המקרים של בעיית 3-SAT בזמן תת־אקספוננציאלי במספר המשתנים. היא משמשת בסיס לחסמי קושי מותנים בבעיות חישוביות נוספות.
האם OpenAI הוכיחה ש־P שווה ל־NP?
לא זו הטענה שפורסמה. הפרכת ETH אינה מחייבת אלגוריתם בזמן פולינומי, ולכן אינה מוכיחה כשלעצמה ש־P=NP; גם טענת ההפרכה עצמה עדיין נתונה לבחינה מחקרית.
האם הפרכת ETH תוביל מיד לתוכנות מהירות יותר?
לא בהכרח. גם אם התוצאה תאומת, יתרון אסימפטוטי עשוי שלא להועיל בגדלי קלט מעשיים, ו־OpenAI מציינת שתרגום התוצאה לאלגוריתמים שימושיים דורש מחקר נוסף.
דרגו את הכתבה
הדירוג עוזר לנו לדעת מה שווה לכם.
תגובות