האם כל טיפש יכול לשער השערות?

אם ה”אישה החוקית” בעולם המתמטיקה הם המשפטים והוכחותיהם, מהם לומד/ת המתמטיקאי/ת את ה”עובדות” – מה נכון ומה לא, הרי ה”פילגש” היא ההשערה – טענה שמתמטיקאי/ת בקי/אה ומנוסה החליט/ה שהיא “בוודאי נכונה”, אחרי שבדק/ה מקרים פרטיים ושקל/ה נימוקים בכובד ראש, והוא/היא מכריז/ה על ההשערה, שבדרך כלל תיקרא על שמו/ה. אבל ללא הוכחה לכאן או לכאן יכולה ההשערה להיות באותה מידה נכונה כמו לא (ואולי אפילו יותר נורא מזה – לא ניתנת להכרעה כלל מהאקסיומות שלנו…), ובתולדות המתמטיקה קרו כל האפשרויות האלו.

וקל להבין (ולהצדיק) את אימרתו המפורסמת של פאול ארדש: “כל טיפש יכול להציע השערות”, אבל זה לא בדיוק כך.

נזכיר כמה השערות בעלות “ערך פיננסי”: בשנת 2000, עם המילניום, החליט מכון קליי \((Clay thinspace Mathematics thinspace Institute)\), מכון פרטי במדינת מסצ’וסטס, ארה”ב, שנוסד אז למען קידום המתמטיקה, להתחיל את פעילותו בהצעת שבעה פרסים, כל אחד בסך מיליון דולר, למי שיפתור שבע בעיות מתמטיות קשות מאוד, ביניהן הוכחת השערות אלו (ולפעמים גם עבור הוכחת אי-נכונותן).

על רבים מוסכם, שהבעיה הלא פתורה הראשונה במעלה במתמטיקה כיום היא הוכחת נכונותה (או הוכחת אי-נכונותה) של השערת רימן  \((Riemann thinspace Hypothesis)\), וזו אחת מבעיות המילניום. היא מנוסחת כהשערה על הערכים בהם מתאפסת פונקציה שנקראת פונקצית זטה (האות היוונית \({zeta}\)) של רימן, שהיא פונקציה מסויימת המוגדרת על מספרים מרוכבים ומקבלת ערכים מרוכבים.

נתאר את השערת רימן בלשונו של מרכוס דו סוטוי \((Marcus thinspace du thinspace Sautoy)\) בספרו “המוזיקה של המספרים הראשוניים”: המספרים הראשוניים מופיעים בין סדרת המספרים הטבעיים באופן שנראה לא סדיר. עם זאת, הם מהווים סדרה המוגדרת באופן יחיד. אם נראה את הופעתם בין המספרים הטבעיים כמוסיקה, הרי הערכים בהם מתאפסת פונקצית זטה של רימן הם התוים, והשערת רימן אומרת שבתזמורת המנגנת מוסיקה זו, כל התוים מנוגנים באותה עוצמה. מטבע הדברים, השערה זו קשורה לאין-ספור טענות הקשורות למספרים הראשוניים ולהתפלגותם בין המספרים הטבעיים.

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

ועוד: את הבדיקות במחשב, כמובן שעשו עם מספרים שאפשר לחשב בהם. אבל ההשערה מדברת על כל אינסוף השורשים של פונקציית זטה. ואפילו אם היינו יכולים לבדוק עד השורש ה-\({10^{1000}}\), עדיין בין \({10^{1000}}\) ואינסוף יש לאין ערוך יותר מספרים מאשר עד \({10^{1000}}\) – את הבדיקה ערכנו בקבוצה “מאוד לא מייצגת” של ה”זאטוטים” הקטנים מ-\({10^{1000}}\). הלא כן?

תורת המספרים, והמספרים הראשוניים בפרט, מצאו מאז שנות השבעים שימוש מפתיע בהצפנה, החל מהדרך בה מכשיר הכספומט יכול לוודא שהוקש מספר סודי נכון בלי שמי שמוצא את הכרטיס יוכל לחשב את המספר הסודי, ועד כל התקשורת הסודית באינטרנט, ועד אפילו שירותי ריגול. בעשרים השנים האחרונות נמצא להם מתחרה בדמות מושג מתמטי, עם דמיון מסויים להם אבל עוד יותר מתוחכם – עקומים אליפטיים סופיים. גם להם יש פונקצית זטה, ואחת מבעיות המילניום היא להכריע השערה לגביה, שנקראת השערת \(Birch\) ו\(Swinnerton-Dyer\). נושאים אלה הם מצד אחד מתמטיקה אזוטרית בעלת יופי מיוחד למי שמכיר אותה, ומצד שני האפשרות או אי האפשרות לפצח את הצפנים שהוזכרו עלולה להיות תלויה בהם.

מה שיכול לפצח חלק גדול מהתקשורת המוצפנת הוא אם ימצאו דרך מהירה לפרק מספר לגורמיו הראשוניים. כאן מדובר במספר “גדול” בעל מאות או אלפי ספרות. במלה “מהירה” מתכוונים לאופן התלות של זמן החישוב באורך הקלט \({ell}\). לגבי נתון מספרי אורך הקלט הוא מספר הספרות (אם רוצים, הבינריות). אם זמן החישוב הוא לא יותר מאורך הקלט בחזקה קבועה (נניח \({ell^3}\) אבל באופן תאורטי מרשים גם \({ell^{100}}\)), אומרים שזמן החישוב פולינומיאלי וזה נחשב לחישוב קל ומהיר. למשל האלגוריתם של אוקלידס מוצא מחלק משותף מקסימלי בזמן פולינומיאלי (כמובן, בלי לפרק לגורמים ראשוניים!). את מחלקת הבעיות שאפשר לפתור בזמן פולינומיאלי מסמנים ב \({textrm{P}}\).

ברור שנוכל למצוא את הגורמים של \({n}\) ע”י בדיקת כל המספרים עד \({n}\), אבל זה ידרוש סדר גודל של \({nsim10^ell}\) פעולות, וזה מעריכי ולא פולינומיאלי. כיום ידועות שיטות לפירוק יותר מהירות ממעריכיות, אבל לא פולינומיאליות, ולכן “עדיין” הצפנים בטוחים. אבל דבר אחד אפשר להגיד: אם מישהו נתן לנו מועמדים לגורמים, דרוש רק זמן פולינומיאלי לבדוק אם אלה אכן גורמים. לבעיות כאלה, בהן בדיקת מועמד לפתרון היא “מהירה”, קוראים \({textrm{NP}}\) מ\(Nondeterministic thinspace Polynomial\) (פולינומיאלי, בתנאי שיש לנו מחשב לא דטרמיניסטי שבודק בבת אחת את כל האפשרויות\({ldots}\)). בדומה לבעיית הפירוק לגורמים, אפשר לפתור בעייה \({textrm{NP}}\) ע”י בדיקת כל האפשרויות, אבל זה ידרוש בדרך כלל זמן מעריכי.

במיוחד, אם ננסח את האקסיומות והלוגיקה של ענף במתמטיקה באופן פורמלי לחלוטין, אזי בדיקה, האם מועמדת להוכחה היא אכן הוכחה, ניתנת לביצוע באופן אוטומטי והיא פולינומיאלית באורך הקלט (שבמקרה זה הוא מספר התוים). לכן הבעיה למצוא למשפט באורך \({ell}\) הוכחה מאורך לא יותר מ \({ell^{100}}\), אם יש כזו, היא \({textrm{NP}}\) (ואם ההוכחה הכי קצרה היא מאורך יותר מ \({ell^{100}}\) איש לא יוכל לכתוב אותה ולכן היא לא קיימת לגבינו). מבחינה זו, “המתמטיקה היא \({textrm{NP}}\)”.

ברור ש \({textrm{P}subsettextrm{NP}}\) (כלומר כל בעיה שהיא \({textrm{P}}\) היא \({textrm{NP}}\), מדוע?) אבל עד כמה שהדבר מוזר, לא ידוע אם \({textrm{NP}}\) לא שווה ל \({textrm{P}}\), כלומר האם אי אפשר לפתור את כל הבעיות ה \({textrm{NP}}\) באופן מהיר, למרות שרוב אנשי מדעי המחשב סבורים ש \({textrm{NP}netextrm{P}}\). השאלה האם \({textrm{NP}=textrm{P}}\) (או, מוטב לאמר, הכרעת ההשערה ש \({textrm{NP}netextrm{P}}\)) היא אחת מבעיות המילניום.

יתר על כן, ע”י ניתוח מופשט מהו למעשה, באופן לוגי, מחשב, הראו רשימה ארוכה של בעיות \({textrm{NP}}\) שנקראות \(NP-complete\) שכל אחת מהן יכולה לתפקד כמין מחשב עד כדי זמן חישוב פולינומיאלי, ולכן אם אפשר לפתור אחת מהן בזמן פולינומיאלי אזי \({textrm{NP}=textrm{P}}\) (ואז, אם נקבל את האמור לעיל על הוכחות פורמליות, “המתמטיקה היא טריוויאלית”\({ldots}\))

ביבליוגרפיה

J.Carlson, A.Jaffe and A.Wiles, ed. The Millennium Prize Problems. Clay Mathematics Institute and American Mathematical Society, 2006.

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

תגובה אחת על האם כל טיפש יכול לשער השערות?

  • מאת אורי‏:

    כתבה מאוד יפה ומתקשרת למדעי המחשב ותורת הסיבוכיות (התחום האהוב עלי). רק אולי בתור אלגוריתם שרץ בזמן פולינומיאלי לא היה כדאי לתת את אלגוריתם אוקלידס משום שזה נכון שהוא רץ בזמן פולינומיאלי אבל אפשר לומר עליו משהו יותר חזק – שהוא רץ בזמן פולילוגריתמי.