בעיית השלשות הפיתגוריות הבוליאנית

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

הבעיה שואלת האם יש צביעה בוליאנית (בשני צבעים, למשל אדום וכחול) של המספרים הטבעיים, כך שלא תימצא אף שלשה פיתגורית שכל שלושת המספרים המרכיבים אותה יהיו באותו צבע. שלשה פיתגורית היא שלשה של מספרים טבעיים $a,b,c$ המקיימת את השוויון $a^{2}+b^{2}=c^{2}$, כמו למשל 3,4,5 או 5,12,13. השאלה היא, אם כך, האם אפשר לצבוע את כל המספרים הטבעיים כך שאחד מבין המספרים 3,4,5 אדום ואחד כחול; אחד מבין המספרים 5,12,13 אדום ואחד כחול; וכן הלאה. מכיוון שיש אינסוף שלשות פיתגוריות, המשימה היא לבחור צבעים לאינסוף מספרים, באופן שיעמוד באינסוף אילוצים.

התברר שהצביעה הנדרשת אינה אפשרית. הפותרים - מרין היולה (Marijn J. H. Heule), אוליבר קולמן (Oliver Kullmann) וויקטור מארק (Victor W. Marek) - הראו כי אפשר לצבוע את המספרים מ-1 עד 7,824, כך שאף אחת מ-19,233 השלשות הפיתגוריות הנמצאות בטווח הזה אינה נצבעת באותו צבע; עם זאת, אי אפשר לצבוע את המספרים מ-1 עד 7,825 בלי ליצור שלשה פיתגורית באותו צבע. כדי להוכיח זאת השאלה נוסחה כבעיית SAT-3 ב-7,825 משתנים, עם אילוץ עבור כל שלשה פיתגורית. מספר הצביעות (או ההשמות) במקרה זה הוא $\ 2^{7,825}$, גודל שאינו מאפשר חיפוש בכוח גס. לאחר צמצום מספר המשתנים ל-3745, הופעלה שיטה לפתרון בעיות ספיקות שידועה כ"שלש ומשול" (Cube and Conquer) שהודגמה כבר כיעילה בעבר ומאפשרת מקביליות. הפותרים הריצו את המערכת על מחשב-על של אוניברסיטת טקסס באוסטין, שעבד על כך במשך יומיים. לבעיות ספיקות שהתשובה עליהן היא שלילית אין בדרך כלל הוכחה קצרה לחוסר הספיקות (הבעיה היא שלמה ל-co-NP). במקרה זה ההוכחה שנוצרה גודלה היה 200 טרה-בית של נתונים, שאותם הצליחו החוקרים לדחוס ל-68 גיגה-בית.

הפותרים פרסמו מאמר המתאר את ההוכחה ב-arXiv ב-3 במאי 2016, והציגו אותה בכנס SAT 2016 שהתקיים ביולי 2016 בבורדו שבצרפת; המאמר קיבל את פרס המאמר המצטיין בכנס. המתמטיקאי רונלד גרהאם, שהבטיח בשנות ה-80 של המאה ה-20 פרס של 100 דולר למי שיפתור את הבעיה, העניק אותו לאחד משלושת השותפים.

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

קישורים חיצוניים

• אלכסנדרה לוקש, אחרי 35 שנה: פתרון לבעיית השלשות הפיתגוריות, פרופסור עוזי וישנה באולפן ynet, באתר ynet, 11 ביולי 2016
• Evelyn Lamb, Two-hundred-terabyte maths proof is largest ever, Nature, 26 May 2016
• Marijn J. H. Heule, Oliver Kullmann, Victor W. Marek, Solving and Verifying the boolean Pythagorean Triples problem via Cube-and-Conquer, arXiv, 3 May 2016

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

33697005בעיית השלשות הפיתגוריות הבוליאנית