OpenAI הודיעה ב־26 באוקטובר 2026 כי מודלים פנימיים שלה מצאו הוכחה המפריכה את השערת הזמן המעריכי, ETH. ההשערה עוסקת בקושי לפתור את בעיית 3-SAT: האם...
OpenAI הודיעה ב־26 באוקטובר 2026 כי מודלים פנימיים שלה מצאו הוכחה המפריכה את השערת הזמן המעריכי, ETH. ההשערה עוסקת בקושי לפתור את בעיית 3-SAT: האם אפשר להציב ערכי אמת ושקר למשתנים כך שאוסף תנאים לוגיים יתקיים. המאמר מציג אלגוריתם שלטענת החברה פותר את הבעיה בזמן תת־מעריכי, ואף סופר את ההצבות המקיימות נוסחאות מסוג רחב יותר. זהו שיפור בקצב שבו זמן החישוב גדל עם הקלט, ולא רק האצה באמצעות חומרה חזקה יותר. [המאמר של OpenAI](https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/build/main_full_version.tex)
מדוע ההכרזה מעוררת עניין? מאות מאמרים הסתמכו על ETH כדי לבסס טענות מותנות על קושי חישובי, בין היתר בתורת הגרפים, במסדי נתונים ובביולוגיה חישובית. אם ההפרכה תאושר, יהיה צורך לבחון מחדש מה אפשר להסיק מהתוצאות האלה, וייפתח מקום לחיפוש אלגוריתמים מהירים יותר. עם זאת, זמן תת־מעריכי עדיין עלול להיות עצום: התוצאה כשלעצמה אינה מוכיחה ש־P=NP ואינה מבטיחה פתרון מעשי ומהיר לכל בעיית אופטימיזציה. [ההכרזה וההקשר המחקרי](https://openai.com/index/building-scientific-understanding-with-academic-communities/)
לצד ההתרגשות, יש כאן גם שאלת אימות. OpenAI מדווחת שפרסמה הוכחה מילולית ופורמליזציה במערכת Lean, והודיעה על קבוצת חוקרים בהובלת ראסל אימפליאצו, רמאמוהן פאטורי וריאן ויליאמס שתבחן ותסביר את העבודה; אימפליאצו ופאטורי נמנים עם מנסחי ההשערה המקוריים. בדיקה פורמלית מדווחת היא צעד משמעותי, אך הבחינה העצמאית והבנת ההשלכות עדיין חיוניות. עבור קהילת הטכנולוגיה, הסיפור הוא גם מבחן ליכולת של AI להפיק מחקר חדש שאפשר לבדוק, להבין ולבנות עליו. [פרטי תהליך הבחינה](https://openai.com/index/building-scientific-understanding-with-academic-communities/)
